链表 part02

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

题目描述

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

示例

输入：head = [1,2,3,4]
输出：[2,1,4,3]

题目链接

https://leetcode.cn/problems/swap-nodes-in-pairs/description/

思路

• 新建一个虚节点，用来指向两两交换后的头节点
• 两节点两两交换

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode node = new ListNode(0);
        node.next = head;
        ListNode temp = node;
        while (temp.next != null && temp.next.next != null) {
            // 两两交换
            ListNode prev = temp.next;
            ListNode cur = temp.next.next;
            // 指向交换后的头节点
            temp.next = cur;
            // 准备进行下一次交换
            prev.next = cur.next;
            cur.next = prev;
            temp = prev;
        }
        return node.next;
    }
}

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

题目描述

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

示例

题目链接

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

解题思路

• 遍历到倒数第 n - 1个节点，删除它的下一节点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int len = 0;
        ListNode node = head;
        while (node != null) {
            len++;
            node = node.next;
        }
        node = new ListNode(0);
        node.next = head;
        ListNode ans = node;
        int count = 0;
        while (node != null && count < len - n) {
            node = node.next;
            count++;
        }
        node.next = node.next.next;
        return ans.next;
    }
}

• 令 fast比 slow先走 n + 1步， 则 fast为空时，slow为倒数第 n个节点的上一节点，删除待删除节点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode node = new ListNode();
        node.next = head;
        ListNode fast = node;
        ListNode slow = node;
        // 提前走 n + 1 步
        while (n-- >= 0) {
            fast = fast.next;
        }
        // fast到终点
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 删除节点
        slow.next = slow.next.next;
        return node.next;
    }
}

面试题 02.07. 链表相交

题目描述

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

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

题目链接

https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/

解题思路

• 两链表化为同剩余长度
• 寻找交点

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0;
        int lenB = 0;
        ListNode nodeA = headA, nodeB = headB;
        // 求两个链表长度
        while (nodeA != null) {
            nodeA = nodeA.next;
            lenA++;
        }
        while (nodeB != null) {
            nodeB = nodeB.next;
            lenB++;
        }
        // 化为同剩余里程
        while (lenA > lenB) {
            headA = headA.next;
            lenA--;
        }
        while (lenB > lenA) {
            headB = headB.next;
            lenB--;
        }
        // 查找交点
        while (headA != null) {
            if (headA.equals(headB)) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}

142.环形链表II

题目描述

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

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

不允许修改 链表。

示例

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

题目链接

https://leetcode.cn/problems/linked-list-cycle-ii/

解题思路

• 判断是否有环
  • fast每次移动两步，slow一步，如果有环，那么两者一定会在某一个节点相遇
  • 如果 fast为空或下一节点为空，则一定无环
• 找到环的位置
  • 设相遇的节点为 meet，起点到入口距离 x，入口到 meet距离 y，meet到入口距离 z
  • 因为两者遇见花费时间一致，所以 (x + y)/1 = (x + y + n * (y + z))/2
  • 化简有 x = n * (y + z) - y
  • n取 1，x = z ; n取 2，x= z + (y + z)
  • 所以从 meet和 head同时同速出发，第一次遇见的地方就是入口

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        boolean hasCircle = false;
        // 判定是否有环
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow.equals(fast)) {
                hasCircle = true;
                break;
            }
        }
        if (!hasCircle) return null;
        ListNode meet = slow;
        ListNode node = head;
        // 求入口
        while (!node.equals(meet)) {
            meet = meet.next;
            node = node.next;
        }
        return node;
    }
}