Day4 | 两两交换链表中的节点 | 删除链表的倒数第N个节点 | 链表相交 | 环形链表II

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

思路：双指针，两个指针一共移动的长度为链表的长度。考虑到头结点可能被删除，所以需要虚拟头结点

特殊情况：如果n大于链表的长度，直接不用删除

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // 思路：双指针，两个指针一共移动的长度为 链表的长度。考虑到头结点可能被删除，所以需要虚拟头结点
    // 特殊情况：如果n大于链表的长度，直接不用删除
    if head == nil {
        return nil
    }
    dummy := &ListNode{}
    dummy.Next = head

    cur := dummy
    for n > 0 {
        if cur.Next != nil {
            cur = cur.Next
        }else {
            return head
        }
        n --
    }
    node := dummy
    for cur.Next != nil {
        cur = cur.Next
        node = node.Next
    }
    node.Next = node.Next.Next
    return dummy.Next
}

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        // 链表长度
        int len = 0;
        ListNode * cur = head;
        while(cur) {
            cur = cur->next;
            len ++;
        }
        ListNode * dummy = new ListNode(0);
        dummy->next = head;
        cur = dummy;
        int idx = len - n;
        while(idx --) {
            cur = cur->next;
        }
        cur->next = cur->next->next;

        return dummy->next;

    }
};

快慢指针方法

简单来说就是两个指针共同走完整条链表

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode * dummy = new ListNode(0);
        dummy->next = head;
        // 快慢指针
        ListNode * slow = dummy;
        ListNode * fast = dummy;

        // 先移动 n + 1 步，这样快指针移动结尾的时候，慢指针刚好移动到需要删除的结点的前面
        int step = n + 1;
        while(step --) fast = fast->next;

        while(fast) {
            fast = fast->next;
            slow = slow->next;
        }

        slow->next = slow->next->next;

        return dummy->next;

    }
};

面试题 02.07. 链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

思路：同时遍历两个链表，如果为空了就从另一个链表的头部开始.

最终相遇的位置肯定是交点位置，因为这个时候走的距离相等

理解：注意循环结束条件即可，如果不想交，那么也会同时走向空节点会退出循环返回null

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    // 思路：同时遍历两个链表，如果为空了就从另一个链表的头部开始，最终相遇的位置肯定是交点位置，因为这个时候走的距离相等
    curA, curB := headA, headB
    for curA != curB {

        if curA != nil {
            curA = curA.Next
        }else {
            curA = headB
        }
        
        if curB != nil {
            curB = curB.Next
        }else {
            curB = headA
        }

    }
    return curA
}

/**
 * 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) {
        if(headB == nullptr || headA == nullptr) return nullptr;
        ListNode * curA = headA;
        ListNode * curB = headB;

        while(curA != curB) {
            if(curA) curA = curA->next;
            else curA = headB;

            if(curB) curB = curB->next;
            else curB = headA;
        }

        return curA;
    }
};

理解：注意循环结束条件即可，如果不想交，那么也会同时走向空节点会退出循环返回null

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

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

思路：引入一个虚拟头结点，虚拟头结点指向第二个节点，第二个节点指向第一个节点，第一个节点指向第三个节点，然后移动两步即可

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    // 思路：引入一个虚拟头结点，虚拟头结点指向第二个节点，第二个节点指向第一个节点，第一个节点指向第三个节点，然后移动两步即可
    if head == nil {
        return nil
    }
    dummy := &ListNode{}
    dummy.Next = head

    head = dummy

    for head.Next != nil && head.Next.Next != nil {
        next := head.Next   
        tmp := head.Next.Next.Next
        // 虚拟头结点指向 第二个节点
        head.Next = head.Next.Next
        // 第二个节点指向第一个节点 反转
        head.Next.Next = next
        // 第一个节点指向第三个节点
        next.Next = tmp
        // 移动两步
        head = head.Next.Next
    }
    return dummy.Next
}

/**
 * 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 * dummy = new ListNode(0);
        dummy->next = head;
        ListNode * cur = dummy;

        while(cur->next && cur->next->next) {
            // 下一个结点改变了，需要保存位置
            ListNode * ne = cur->next;
            // 保存下三个节点，给第三步使用
            ListNode * neNe = cur->next->next->next;

            // 第一步：虚拟头结点指向第二个节点
            cur->next = cur->next->next;
            // 第二步：第二个节点指向第一个节点，反转
            cur->next->next = ne;
            // 第三步：第一个节点指向第三个节点，进入下一组
            ne->next = neNe;

            // 移动两步
            cur = cur->next->next;
        }

        return dummy->next;
    }
};

理解：最重要的就是循环的条件，之后必须要有两个节点才循环。画图理解三个步骤，保存临时节点。

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

思路：快慢指针，相遇的时候，f = 2s; f = s + kn; 可得 s=kn. 所以相遇的时候让快指针从头走m步，恰好相遇的地方就是环开始的地方

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    // 思路：快慢指针，相遇的时候，f = 2s; f = s + kn; 可得 s=kn.
    // 所以相遇的时候让快指针从头走m步
    if head == nil {
        return nil
    }
    fast, slow := head, head
    for {
        if fast.Next != nil && fast.Next.Next != nil {
            fast = fast.Next.Next
            slow = slow.Next
        }else {
            return nil
        }
        // 放在后面避免 开始就退出了
        if fast == slow {
            break
        }
    }
    fast = head
    for fast != slow {
        fast = fast.Next
        slow = slow.Next
    }
    return fast
}

C++ 实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == nullptr) return nullptr;

        ListNode * slow = head;
        ListNode * fast = head;

        while(1) {
            if(fast == nullptr || fast->next == nullptr) {
                return nullptr;
            }
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) {
                break;
            }
        }

        fast = head;
        while(fast != slow) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

理解

没有环直接返回nil；有环的话，如果进入环之前有a个，内有b个；分别走f，s步

相遇的时候有：

f=2s （快指针每次2步，路程刚好2倍）
f = s + nb (相遇时，刚好多走了n圈）

推出：s = nb

从head结点走到入环点需要走： a + nb，而slow已经走了nb，那么slow再走a步就是入环点了。

如何知道slow刚好走了a步？从head开始，和slow指针一起走，相遇时刚好就是a步

链表总结

链表最重要的就是虚拟头结点的使用了，然后就是快慢双指针

目录CONTENT

Day4 | 两两交换链表中的节点 | 删除链表的倒数第N个节点 | 链表相交 | 环形链表II

Day4 | 两两交换链表中的节点 | 删除链表的倒数第N个节点 | 链表相交 | 环形链表II

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

面试题 02.07. 链表相交

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

142. 环形链表 II

链表总结

评论区