首页 计算机科学 算法 LeetCode

# 两两交换链表中的节点

题目链接🔗

涉及到对头节点的处理，使用虚拟头节点来统一节点的处理逻辑。

初始时，cur 指向虚拟头节点，然后进行如下三步：

两两交换链表中的节点

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向 head，这样方便后面做删除操作
        ListNode* cur = dummyHead;
        while(cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* tmp1 = cur->next; // 记录临时节点
            ListNode* tmp2 = cur->next->next->next; // 记录临时节点
            cur->next = cur->next->next;    // 步骤一
            cur->next->next = tmp1;          // 步骤二
            cur->next->next->next = tmp2;   // 步骤三
            cur = cur->next->next; //cur 移动两位，准备下一轮交换
        }
        return dummyHead->next;
    }
};
# 删除链表的倒数第 N 个节点
题目链接🔗
双指针经典题。如果要删除倒数第 n 个节点，让 fast 指针移动 n 步，然后让 fast 和 slow 指针同时移动，直到 fast 指向链表末尾。删掉 slow 所指向的节点即可。
  • 使用虚拟头节点，方便处理删除实际头节点的罗辑
  • 定义 fast 和 slow 指针，初始位置为虚拟头节点
    初始状态
  • fast 先走 n+1 步。只有这样同时移动的时候 slow 才嫩指向要删除节点的上一个节点，方便操作。
    先移动fast
  • fast 和 slow 同时移动，直到 fast 指向末尾
    同时移动
  • 删除 slow 指向的下一个节点
    删除
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        /* 初始状态 */
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* slow = dummyHead;
        ListNode* fast = dummyHead;
        /* 先移动 fast */
        while(n-- && fast != nullptr)
            fast = fast->next;
        fast = fast->next;
        /* 同时移动 */
        while(fast != nullptr){
            fast = fast->next;
            slow = slow->next;
        }
        /* 删除 */
        ListNode *tmp = slow->next;
        slow->next = tmp->next;
        delete tmp;
        return dummyHead->next;
    }
};
# 链表相交
题目链接🔗
链表相交的交点是指针相等。
如果链表 A 和链表 B 相交于 D 的话，那么说明 D 节点即在 A 上又在 B 上，而 D 之后的元素自然也就均在 A 和 B 上了，因为他们是通过 next 指针相连的。
# 代码随想录解法
对其两个链表的尾部：求出两个链表的长度，并求出两个链表长度的差值，然后让 curA 移动到，和 curB 末尾对齐的位置，
对其尾部
此时我们就可以比较 curA 和 curB 是否相同，如果不相同，同时向后移动 curA 和 curB，如果遇到 curA == curB，则找到交点。
否则循环退出返回空指针。
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != NULL) { // 求链表 A 的长度
            lenA++;
            curA = curA->next;
        }
        while (curB != NULL) { // 求链表 B 的长度
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;
        // 让 curA 为最长链表的头，lenA 为其长度
        if (lenB > lenA) {
            swap (lenA, lenB);
            swap (curA, curB);
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让 curA 和 curB 在同一起点上（末尾位置对齐）
        while (gap--) {
            curA = curA->next;
        }
        // 遍历 curA 和 curB，遇到相同则直接返回
        while (curA != NULL) {
            if (curA == curB) {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;
    }
};
# leetcode 解法
设「第一个公共节点」为 node ，「链表 headA 」的节点数量为 a ，「链表 headB」的节点数量为 b ，「两链表的公共尾部」的节点数量为 c ，则有：
  • 头节点 headA 到 node 前，共有a−ca-c 个节点；
  • 头节点 headB 到 node 前，共有b−cb-c 个节点；
解释
构建两个指针分别指向两链表头节点做如下操作：
  • 指针 A 先遍历链表 headA ，再开始遍历 headB ，走到 node 时，共走步数为：
a+(b−c)a+(b-c)
  • 指针 B 先遍历链表 headB ，再开始遍历 headA ，走到 node 时，共走步数为：
b+(a−c)b+(a-c)
当两指针重合时，有两种情况：
a+(b−c)=b+(a−c)a+(b-c) = b+(a-c)
  1. 若两链表 有 公共尾部 (即 c>0c>0 ) ：指针同时指向「第一个公共节点 node 。
  2. 若两链表 无 公共尾部 (即 c=0c=0) ：指针同时指向 nullptr 。
因此返回 A 即可。
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *A = headA, *B = headB;
        while (A != B) {
            A = A != nullptr ? A->next : headB;
            B = B != nullptr ? B->next : headA;
        }
        return A;
    }
};
# 环形链表
题目链接🔗
主要考察两个知识点：
  • 判断链表是否有环
  • 如果有环，如何找到入口
# 判断链表是否有环
用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发， fast 指针每次移动两个节点， slow 指针每次移动一个节点，如果 fast 和 slow 指针在途中相遇 ，说明这个链表有环。
fast 指针一定先进入环中，如果 fast 指针和 slow 指针相遇的话，一定是在环中相遇，这是毋庸置疑的。
这是因为 fast 是走两步， slow 是走一步，其实相对于 slow 来说， fast 是一个节点一个节点的靠近 slow 的，所以 fast 一定可以和 slow 重合。
快慢指针相遇
# 如果有环，如何找到入口
假设从头结点到环形入口节点的节点数为 x。 环形入口节点到 fast 指针与 slow 指针相遇节点节点数为 y。从相遇节点 再到环形入口节点节点数为 z。 如图所示：
那么相遇的时候，slow 走过的节点数为：x+yx+y，fast 走过的节点数为：x+n(y+z)+yx+n(y+z)+y，n 为 fast 在环内走了 n 圈才和 slow 相遇
因为 fast 一次走两个节点，slow 一次走一个节点，所以 fast走过的节点数=slow走过的节点数*2 ：
(x+y)∗2=x+n(y+z)+y(x + y) * 2 = x + n(y+z) + y
两边消去一个 x+y ：
x+y=n(y+z)x + y = n(y + z)
因为要找入口，求的是 x，因此：
x=n(y+z)−yx = n(y+z)-y
再从 n(y+z) 中提取一个 (y+z) ，最后公式如下：
x=(n−1)(y+z)+zx = (n - 1)(y + z) + z
当n=1n = 1 的时候，公式就化解为x=zx = z，
这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点，那么当这两个指针相遇的时候就是环形入口的节点。
那么 n 如果大于 1 是什么情况呢，就是 fast 指针在环形转 n 圈之后才遇到 slow 指针。
其实这种情况和 n=1 的时候效果是一样的，一样可以通过这个方法找到环形的入口节点，只不过，环里的指针多转了 (n-1) 圈，然后再遇到与另一个指针，相遇点依然是环形的入口节点。
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指针相遇，此时从 head 和 相遇点，同时查找直至相遇
            if (slow == fast) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2; // 返回环的入口
            }
        }
        return NULL;
    }
};