1 给定单链表，检测是否有环。

      使用两个指针p1,p2从链表头开始遍历，p1每次前进一步，p2每次前进两步。如果p2到达链表尾部，说明无环，否则p1、p2必然会在某个时刻相遇(p1==p2)，从而检测到链表中有环。

1 struct Node 2 { 3     int val; 4     Node * next; 5     Node(int _val=0,Node * _next=NULL) 6     { 7         val = _val; 8         next = _next; 9     }10 };11 12 bool isLinklistHasLoop(Node * head)13 {14     Node * p1 = head, *p2 = head;15     while(true)16     {17         if (p1 == NULL)18         {19             return false;20         }21         else22         {23             p1 = p1->next;24         }25         if (p2 == NULL || p2->next == NULL)26         {27             return false;28         }29         else30         {31             p2 = p2->next->next;32         }33         if (p1 == p2)34         {35             return true;36         }37     }38 }

 

2 给定两个单链表(head1, head2)，检测两个链表是否有交点，如果有返回第一个交点。

如果head1==head2，那么显然相交，直接返回head1。否则，分别从head1,head2开始遍历两个链表获得其长度len1与len2，假设len1>=len2，那么指针p1由head1开始向后移动len1-len2步，指针p2=head2，下面p1、p2每次向后前进一步并比较p1p2是否相等，如果相等即返回该结点，否则说明两个链表没有交点。

1 int getLinklistLength(Node * head) 2 { 3     int cnt = 0; 4     Node * p = head; 5     while(head != NULL) 6     { 7         cnt++; 8         head = head->next; 9     }10     return cnt;11 }12 13 Node * getFirstIntersectNode(Node * head1,Node * head2)14 {15     if (head1 == head2)16     {17         return head1;18     }19     int len1 = getLinklistLength(head1);20     int len2 = getLinklistLength(head2);21     Node * p1 = head1, * p2 = head2;22     if (len1 >= len2)23     {24         for (int i=1; i<=len1-len2; i++)25         {26             p1 = p1->next;27         }28     }29     else30     {31         for (int i=1; i<=len2-len1; i++)32         {33             p2 = p2->next;34         }35     }36     while(p1 != NULL && p2 != NULL)37     {38         if (p1 == p2)39         {40             return p1;41         }42         p1 = p1->next;43         p2 = p2->next;44     }45     if (p1==NULL || p2==NULL)46     {47         return NULL;48     }49 }

 

3 给定单链表(head)，如果有环的话请返回从头结点进入环的第一个节点。

        运用题一，我们可以检查链表中是否有环。如果有环，那么p1p2重合点p必然在环中。从p点断开环，方法为：p1=p, p2=p->next, p->next=NULL。此时，原单链表可以看作两条单链表，一条从head开始，另一条从p2开始，于是运用题二的方法，我们找到它们的第一个交点即为所求。

 

4 只给定单链表中某个结点p(并非最后一个结点，即p->next!=NULL)指针，删除该结点。

       首先是放p中数据,然后将p->next的数据copy入p中，接下来删除p->next即可。

1 void deleteNode(Node * node)2 {3     Node * nextNode = node->next;4     node->val = nextNode->val;5     node->next = nextNode->next;6     delete nextNode;7 }

 

 

5 只给定单链表中某个结点p(非空结点)，在p前面插入一个结点。

        办法与前者类似，首先分配一个结点q，将q插入在p后，接下来将p中的数据copy入q中，然后再将要插入的数据记录在p中。

1 template
     
       2 void tmpSwap(T & a,T & b) 3 { 4     T tmp = a; 5     a = b; 6     b = tmp; 7 } 8  9 void insertNode(Node * curNode,Node * newNode)10 {11     newNode->next = curNode->next;12     curNode->next = newNode;13     tmpSwap(curNode->val,newNode->val);14 }
     

 

 

6 单链表的逆置

两种方法，非递归和递归

1 void loopReverseLinklist(Node * & head) 2 { 3     Node * preNode = head; 4     Node * curNode = preNode->next; 5     Node * nextNode = NULL; 6     while(curNode != NULL) 7     { 8         nextNode = curNode->next; 9         curNode->next = preNode;10         preNode = curNode;11         curNode = nextNode;12     }13     head->next = NULL;14     head = preNode;15 }16 17 void dfsReverseLinklist(Node * & head,Node * curNode)18 {19     if (curNode == NULL || curNode->next == NULL)20     {21         head = curNode;22         return;23     }24     Node * nextNode = curNode->next;25     dfsReverseLinklist(head,nextNode);26     nextNode->next = curNode;27     curNode->next = NULL;28 }

另外，带返回值的方法如下：

1 Node * loopReverse(Node * node) 2 { 3     if (node == NULL || node->next == NULL) 4     { 5         return node; 6     } 7     Node * prePt = node, * curPt = prePt->next; 8     Node * nextPt = NULL; 9     while(curPt != NULL)10     {11         nextPt = curPt->next;12         curPt->next = prePt;13         prePt = curPt;14         curPt = nextPt;15     }16     node->next = NULL;17     return prePt;18 }19 20 21 Node * dfsReverse(Node * node)22 {23     if (node == NULL || node->next == NULL)24     {25         return node;26     }27     Node * nextNode = dfsReverse(node->next);28     node->next->next = node;29     node->next = NULL;30     return nextNode;31 }

 

7 单链表找出中间节点

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

1 Node * findMidNode(Node * head) 2 { 3     if (head == NULL || head->next == NULL) 4     { 5         return head; 6     } 7     Node * p1 = head, * p2 = head; 8     while(true) 9     {10         if (p2->next != NULL && p2->next->next != NULL)11         {12             p2 = p2->next->next;13             p1 = p1->next;14         }15         else16         {17             break;18         }19     }20     return p1;21 }

8 已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序。(保留所有结点，即便大小相同）

两种方法，非递归和递归

1 Node * loopMergeLinklist(Node * head1,Node * head2) 2 { 3     if (head1 == NULL && head2 != NULL) 4     { 5         return head2; 6     } 7     if (head1 != NULL && head2 == NULL) 8     { 9         return head1;10     }11     if (head1 == NULL && head2 == NULL)12     {13         return NULL;14     }15     Node * p1 = head1, * p2 = head2;16     Node * newLinklist, * pNode;17     if (head1->val <= head2->val)18     {19         newLinklist = head1;20         pNode = head1;21         p1 = p1->next;22     }23     else24     {25         newLinklist = head2;26         pNode = head2;27         p2 = p2->next;28     }29     while(p1 != NULL && p2 != NULL)30     {31         if (p1->val <= p2->val)32         {33             pNode->next = p1;34             p1 = p1->next;35         }36         else37         {38             pNode->next = p2;39             p2 = p2->next;40         }41         pNode = pNode->next;42     }43     if (p1 != NULL)44     {45         pNode->next = p1;46     }47     else48     {49         pNode->next = p2;50     }51     return newLinklist;52 }53 54 Node * dfsMergeLinklist(Node * head1,Node * head2)55 {56     if (head1 == NULL)57     {58         return head2;59     }60     if (head2 == NULL)61     {62         return head1;63     }64     Node * newLinklist = NULL;65     if (head1->val < head2->val)66     {67         newLinklist = head1;68         newLinklist->next = dfsMergeLinklist(head1->next,head2);69     }70     else71     {72         newLinklist = head2;73         newLinklist->next = dfsMergeLinklist(head1,head2->next);74     }75     return newLinklist;76 }

 

 

9 有一个链表L,其每个节点有2个指针，一个指针next指向链表的下个节点，另一个random随机指向链表中的任一个节点，可能是自己或者为空，写一个程序，要求复制这个链表的结构并分析其复杂性

这个题目的方法很巧妙，将两个链表连接起来形成一个链表，设置好random指针后再将两个链表分割开来。

1 ComplexNode * copyRndList(ComplexNode * head) 2 { 3     ComplexNode * newHead = NULL; 4     ComplexNode * newCurPtr = NULL; 5     ComplexNode * curPtr = head; 6     while(curPtr != NULL) 7     { 8         if (newHead == NULL) 9         {10             newHead = new ComplexNode;11             newHead->nextPtr = curPtr->nextPtr;12             newHead->val = curPtr->val;13             curPtr->nextPtr = newHead;14         }15         else16         {17             newCurPtr = new ComplexNode;18             newCurPtr->nextPtr = curPtr->nextPtr;19             newCurPtr->val = curPtr->val;20             curPtr->nextPtr = newCurPtr;21         }22         curPtr = curPtr->nextPtr->nextPtr;23     }24     curPtr = head;25     while(curPtr != NULL)26     {27         if (curPtr->randPtr != NULL)28         {29             curPtr->nextPtr->randPtr = curPtr->randPtr->nextPtr;30         }31         else32         {33             curPtr->nextPtr->randPtr = NULL;34         }35         curPtr = curPtr->nextPtr->nextPtr;36     }37     curPtr = head;38     ComplexNode * dst = curPtr->nextPtr;39     while(curPtr != NULL)40     {41         ComplexNode * tmp = dst->nextPtr;42         curPtr->nextPtr = tmp;43         if (tmp)44         {45             dst->nextPtr = tmp->nextPtr;46         }47         curPtr = curPtr->nextPtr;48         dst = dst->nextPtr;49     }50     return newHead;51 }