代码随想录算法训练营第四天 | ●24. 两两交换链表的节点 19.删除链表的倒数第N个节点160.链表相交142.环形链表II18期

24. 两两交换链表中的节点

思路：加入一个虚拟头节点，再通过虚拟头节点将之后两个节点更换位置，将虚拟头节点之后的第一个节点用指针tmp指向它，用tmp1指向第二个节点之后的位置（可能是一个节点也可能是NULL）,按照代码随想录里的顺序就可以了。

1.  
   ListNode* swapPairs(ListNode* head) {
2.  
    
3.  
   ListNode* pNode = new ListNode(0);
4.  
   pNode->next = head;
5.  
   ListNode* cur = pNode;
6.  
   while(cur->next!= NULL && cur->next->next!=NULL ){
7.  
   ListNode* tmp = cur->next;
8.  
   ListNode* tmp1= cur->next->next->next;
9.  
    
10.  
    cur->next = tmp->next;
11.  
    cur->next->next = tmp;
12.  
    cur->next->next->next = tmp1;
13.  
     
14.  
    cur = cur->next->next;
15.  
     
16.  
    }
17.  
     
18.  
    head = pNode->next;
19.  
    delete pNode;
20.  
    return head;
21.  
     
22.  
    }

19.删除链表的倒数第N个节点

通过双指针里，快指针先走n 1步，慢指针指向虚拟头节点，同时走，直到快指针走到链表的末尾，突出一个相对距离。就是两个指针相距n 1个链表节点，这样子就能够找到倒数n个节点，就像一个能存n个节点的窗口，右边界碰到末尾的NULL，左边界也就是要找的倒数n个节点。

1.  
   ListNode* removeNthFromEnd(ListNode* head, int n) {
2.  
   ListNode* vhead = new ListNode(0);
3.  
   vhead->next = head;
4.  
   ListNode* fhead = vhead;
5.  
   ListNode* lhead = vhead;
6.  
   while(n-- && fhead != NULL){
7.  
   fhead = fhead->next;
8.  
   }
9.  
   fhead = fhead->next;
10.  
    while(fhead != NULL){
11.  
    fhead = fhead->next;
12.  
    lhead = lhead->next;
13.  
    }
14.  
    lhead->next = lhead->next->next;
15.  
     
16.  
     
17.  
    return vhead->next;
18.  
    }

160.链表相交

通过计算两个链表的长度，并算出差值n，则可让他们从同时倒数第n个节点同时往后遍历，这样一定能够同时到达交叉的节点。

1.  
   ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
2.  
    
3.  
   //1、先算出两个链表的长度 lenA lenB,得出它的差值n
4.  
   ListNode * pheadA = headA;
5.  
   ListNode * pheadB = headB;
6.  
   int lenA = 0;
7.  
   int lenB = 0;
8.  
    
9.  
   while(pheadA != NULL){
10.  
    pheadA = pheadA->next;
11.  
    lenA ;
12.  
    }
13.  
     
14.  
    while(pheadB != NULL){
15.  
    pheadB = pheadB->next;
16.  
    lenB ;
17.  
    }
18.  
     
19.  
    pheadA = headA;
20.  
    pheadB = headB;
21.  
     
22.  
    int n = 0;
23.  
    if(lenA >= lenB){
24.  
    n = lenA - lenB;
25.  
    while(n--){
26.  
    pheadA = pheadA->next;
27.  
    }
28.  
     
29.  
    }
30.  
    else
31.  
    {
32.  
    n = lenB- lenA;
33.  
    while(n--){
34.  
    pheadB = pheadB->next;
35.  
    }
36.  
    }
37.  
     
38.  
     
39.  
    //2、使得他们从距离尾节点相同距离的n个节点开始往后遍历，直到到达互相包含的节点
40.  
     
41.  
    while(pheadA != NULL){
42.  
    if(pheadA == pheadB) return pheadA;
43.  
    pheadA = pheadA->next;
44.  
    pheadB = pheadB->next;
45.  
    }
46.  
     
47.  
    return NULL;
48.  
     
49.  
     
50.  
     
51.  
    }

142.环形链表II

      一个快指针一次走两步，一个慢指针一次走一步，如果不会走到NULL,且他们相遇，那么就证明有环。

如果有环，则可以让一个从首节点出发，一个从相遇节点出发，他们会在入口节点相遇。

由下可以得出x等于若干圈环加上一个z,所以他们一定会在入口节点相遇。

代码随想录

1.  
   ListNode *detectCycle(ListNode *head) {
2.  
   ListNode* Fhead = head;
3.  
   ListNode* Lhead = head;
4.  
    
5.  
   while(Fhead!=NULL && Fhead->next != NULL){
6.  
   Fhead = Fhead->next->next;
7.  
   Lhead = Lhead->next;
8.  
   if(Fhead == Lhead){
9.  
   ListNode* index1 = Fhead;
10.  
    ListNode* index2 = head;
11.  
    while(index1 != index2){
12.  
    index1 = index1->next;
13.  
    index2 = index2->next;
14.  
    }
15.  
    return index1;
16.  
     
17.  
    }
18.  
     
19.  
    }
20.  
     
21.  
    return NULL;
22.  
     
23.  
     
24.  
     
25.  
    }

dd

这篇好文章是转载于：学新通技术网