链表面试题_给定一个n的链表,m次操作。每次操作为下列操作之一。输出m次操作后的链表

给出非递归和递归解法：

#include <iostream>

using namespace std;

struct Node
{
int data;
Node* next;
}*head;

// 非递归写法
Node* InverseLinkedList(Node* head)
{
if(head == NULL)
return NULL;
Node* newHead = NULL;
while(head != NULL)
{
Node* nextNode = head->next;
head->next = newHead;
newHead = head;
head = nextNode;
}
return newHead;
}

// 递归写法
Node* InverseLinkedListRecur(Node* head)
{
if(head == NULL)
return NULL;
if(head->next == NULL)
return head;
Node* newHead = InverseLinkedListRecur(head->next);
Node *tmp = newHead;
while(tmp->next != NULL)
{
tmp = tmp->next;
}
tmp->next = head;
head->next = NULL;
return newHead;
}

int main()
{
// 构建链表 9->8->7->6->5->4->3->2->1->0->NULL
for(int i = 0; i < 10; i++)
{
Node* node = new Node();
node->data = i;
node->next = head;
head = node;
}
head = InverseLinkedList(head);
Node *tmp = head;
while(head != NULL)
{
cout << head->data << " ";
head = head->next;
}
cout << endl;
head = InverseLinkedListRecur(tmp);
tmp = head;
while(head != NULL)
{
cout << head->data << " ";
head = head->next;
}
cout << endl;
while(tmp != NULL)
{
Node* next = tmp->next;
delete tmp;
tmp = next;
}
}
题九、两个有序链表的合并

有两个有序链表，各自内部是有序的，但是两个链表之间是无序的

typedef struct node{
     int data;
     struct node * next;
}* List;
 
List mergeSortedLinkList(List list1, List list2)
{
     List pList1,pList2,mergedList,pCurNode;
 
     if (list1 == NULL)
     {
         return list2;
     }
     if (list2 == NULL)
     {
         return list1;
     }
 
     pList1 = list1;
     pList2 = list2;
     mergedList = NULL;
     if (pList1==pList2)
     {       
        mergedList = pList1;
         pList1 = pList1->next;
         pList2 = pList2->next;
     }
     else 
    {
         if (pList1->data <= pList2->data)
         {
             mergedList = pList1;
             pList1 = pList1->next;
         }
         else
         {
             mergedList = pList2;
             pList2 = pList2->next;
         }
     }
     pCurNode = mergedList;
     while(pList1 && pList2)
     {
         if (pList1==pList2)
         {
             pCurNode->next = pList1;
             pCurNode = pList1;
             pList1 = pList1->next;
             pList2 = pList2->next;
         }
         else
         {
             if (pList1->data <= pList2->data)
             {
                 pCurNode->next = pList1;
                 pCurNode = pList1;
                 pList1 = pList1->next;
             }
             else
             {
                 pCurNode->next = pList2;
                 pCurNode = pList2;
                 pList2 = pList2->next;
             }
         }
     }
 
     pCurNode->next =pList1?pList1:pList2;
 
     return mergedList;
}
 题十、找出链表的中间元素 

单链表的一个比较大的特点用一句广告语来说就是“不走回头路”，不能实现随机存取（random access）。如果我们想要找一个数组a的中间元素，直接a[len/2]就可以了，但是链表不行，因为只有a[len/2 - 1] 知道a[len/2]在哪儿，其他人不知道。因此，如果按照数组的做法依样画葫芦，要找到链表的中点，我们需要做两步（1）知道链表有多长（2）从头结点开始顺序遍历到链表长度的一半的位置。这就需要1.5n（n为链表的长度）的时间复杂度了。有没有更好的办法呢？有的。想法很简单：两个人赛跑，如果A的速度是B的两倍的话，当A到终点的时候，B应该刚到中点。这只需要遍历一遍链表就行了，还不用计算链表的长度。