● 24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 ● 面试题 02.07. 链表相交 ● 142.环形链表II ● 总结

两两交换链表中的节点

C++

alt

首先明确操作的循环区间，cur指向要交换的两个节点的前一个节点才能保证循环不变性，可以理解成链表的左闭右开区间，虚拟头结点就是为了满足循环不变性。终止条件考虑奇偶cur->next,cur->next->next都不为空。如果按图里面1,2,3的顺序可以省一个临时变量。另外循环条件有两层next，那循环内部取三次next就是合法的，只不过取出来的有可能是null。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* virtualHead = new ListNode(-1);
        ListNode* cur = virtualHead;
        while(cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* tmp = cur->next;
            cur->next = cur->next->next;
            tmp->next = cur->next->next;
            cur->next->next = tmp;
            cur = cur->next->next;
        }
        return virtualHead->next;
    }
};

C#

按照1->3->2顺序，但得多用一个临时变量。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode SwapPairs(ListNode head) {
        ListNode virtualHead = new ListNode(-1);
        virtualHead.next = head;
        ListNode cur = virtualHead;
        while(cur.next != null && cur.next.next != null) {
            ListNode tmp = cur.next;
            ListNode tmp1 = cur.next.next.next;
            cur.next = cur.next.next;
            cur.next.next = tmp;
            tmp.next = tmp1;
            cur = cur.next.next;
        }
        return virtualHead.next;
    }
}

删除链表的倒数第 N 个结点

C+

双指针，快的线先动，慢的再一起动，注意从虚拟头结点开始，fast要先走n+1步这样slow指向的是倒数第N + 1个节点，这样才能删除第N个,一起动的时候判断条件为fast->next!=null就可以提前停下了。

public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        ListNode virtualHead = new ListNode(-1);
        virtualHead.next = head;
        ListNode slow = virtualHead;
        ListNode fast = virtualHead;
        while(n-- > 0) {
            fast = fast.next;
        }
        while(fast.next != null) {
            fast =fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return virtualHead.next;
    }
}

C#

链表相交

C++

题第一眼看挺怪的，注意相交指的是指针相同（引用完全相同，即：内存地址完全相同的交点），不是指针的值相同，并且后面的节点都一样。先获取长度，后对齐遍历即可。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int lenA = 0;
        int lenB = 0;
        while(curA != nullptr) {
            lenA++;
            curA = curA->next;
        }
        while(curB != nullptr) {
            lenB++;
            curB= curB->next;
        }
        curA = headA;
        curB = headB;
        int cnt = 0;
        if(lenA >= lenB) {
            cnt = lenA - lenB;
            while(cnt--) {
                curA = curA->next;
            }
        } else {
            cnt = lenB - lenA;
            while(cnt--) {
                curB = curB->next;
            }
        }
        while(curA != nullptr) {
            if(curA == curB) {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return nullptr;
    }
};

C#

环形链表

slow（每次移动一步）和fast（每次移动两步）快慢指针判断是否有环，根据数学公式推理出相遇点和链表头同时移动，再次相遇时就是链表入口。

只有有环，快慢指针才会相遇。
快指针相当于慢指针每次移动一个节点，一定会相遇，不会跳过。
快慢指针相遇时，满指针一定还在第一圈，应为慢指针走过一圈，快指针就走了两圈套娃恰好相遇，此临界状态慢指针也在第一圈，更不要说如果快指针提前走了，追的会更快，肯定会提前相遇。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) {
                ListNode* L1 = head;
                ListNode* L2 = fast;
                while(L1 != L2) {
                    L1 = L1->next;
                    L2 = L2->next;
                }
                return L1;
            }
        }
        return nullptr;
    }
};

C#

public class Solution {
    public ListNode DetectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow) {
                ListNode L1 = fast;
                ListNode L2 = head;
                while(1 > 0) {
                    if(L1 == L2) {
                        return L1;
                    }
                    L1 = L1.next;
                    L2 = L2.next;
                }
            }
        }
        return null;
    }
}

二刷

两两交换链表中的绩点

使用虚拟头结点，注意while循环条件。


struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
 };

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* virtualHead = new ListNode(-1);
        virtualHead->next = head;
        ListNode* cur = virtualHead;
        while (cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* temp = cur->next;
            cur->next = temp->next;
            temp->next = cur->next->next;
            cur->next->next = temp;
            cur = temp;
        }
        return virtualHead->next;
    }
};

删除倒数第N个节点

#include<iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int val): val(val), next(nullptr){ }
};
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* vH = new ListNode(-1);
        vH->next = head;
        ListNode* fast = vH;
        ListNode* slow = vH;
        for (int i = 0; i <= n; i++) {
            fast = fast->next;
        }
        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        ListNode* temp = slow->next;
        slow->next = slow->next->next;
        delete temp;
        return vH->next;
    }
};

ListNode* ListNodeIn() {
    ListNode* head = new ListNode(-1);
    int n = 0;
    cin >> n;
    ListNode* cur = head;
    for (int i = 1; i <= n; i++) {
        int temp = 0;
        cin >> temp;
        ListNode* tt = new ListNode(temp);
        cur->next = tt;
        cur = cur->next;
    }
    return head->next;
}

void ListNodeOut(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        head = head->next;
    }
}
int main() {
    ListNode* head = ListNodeIn();
    Solution s1;
    ListNode* ans = s1.removeNthFromEnd(head, 2);
    ListNodeOut(ans);
    return 0;
}

链表相交

注意下相交是指指针相等，而不是指针指向的对象值相等。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = 0;
        ListNode* curA = headA;
        while (curA != nullptr) {
            lenA++;
            curA = curA->next;
        }
        int lenB = 0;
        ListNode* curB = headB;
        while(curB != nullptr) {
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;
        //对齐起始位置
        if (lenA <= lenB) {
            int cnt = lenB - lenA;
            //B长，移动B指针
            for (int i = 0; i < cnt; i++) {
                curB = curB->next;
            }
        }
        else {
            int cnt = lenA - lenB;
            //A长，移动A指针
            for (int i = 0; i < cnt; i++) {
                curA = curA->next;
            }
        }

        while (curA != nullptr) {
            if (curA== curB) {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return nullptr;

    }
};

环形链表

哈希表耍赖。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode*> data;
        ListNode* cur = head;
        while (cur != nullptr) {
            if (data.find(cur) == data.end()) {
                data.insert(cur);
            }
            else {
                return cur;
            }
            cur = cur->next;
        }
        return nullptr;
    }
};

快慢指针


struct ListNode {
    int val;
    ListNode* next;
    ListNode(int val): val(val), next(nullptr){ }
};
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (fast == slow) {
                ListNode* cur = head;
                while (slow != cur) {
                    cur = cur->next;
                    slow = slow->next;
                }
                return cur;
            }
        }

        return nullptr;
    }
};

链表总结

很重要的一点，遍历条件终止是cur还是cur->next看要不要对最后一个节点进行操作，如果不需要操作最后一个节点，仅仅是让节点索引停在最后一个点，那用cur->next,因为索引虽然到了最后一个节点，但已经不符合条件跳出循环，并不会对节点进行操作。
循环中如果有用到cur->next->next->next，则要保证cur->next->next不为空，如果cur每次循环跳两步，则先要保证cur->next不为空，快慢指针经常用到。
cur可以从虚拟头结点出发，这样遍历可以控制停在待修改点的前驱节点，方便进行操作，比如删除节点，cur就要停在前一个。

虚拟头可以避免对头结点修改和链表为空情况的单独讨论，只有当对头结点进行操作时需要用，遍历则不需要虚拟头结点。

alt

[代码随想录一刷&二刷] day4 链表

两两交换链表中的节点

C++

C#

删除链表的倒数第 N 个结点

C+

C#

链表相交

C++

C#

环形链表

C#

二刷

两两交换链表中的绩点

删除倒数第N个节点

链表相交

环形链表

链表总结