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

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

方法：

• 递归
  返回值：交换完成的子链表
  调用单元：设需要交换的两个点为 head 和 next，head 连接后面交换完成的子链表，next 连接 head，完成交换
  终止条件：head 为空指针或者 next 为空指针，也就是当前无节点或者只有一个节点，无法进行交换

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 递归终止    条件：head 为空指针或者 next 为空指针，也就是当前无节点或者只有一个节点，无法进行交换
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        // head 连接后面交换完成的子链表
        head.next = swapPairs(next.next);
        // next 连接 head，完成交换
        next.next = head;
        // 新头节点
        return next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 非递归写法

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 虚拟头节点
        ListNode dummyNode = new ListNode(-1, head);
        ListNode pre = dummyNode;
        while(pre.next != null && pre.next.next != null){
            // 俩节点互换前先临时保存后面子链的头节点
            ListNode tempNode = head.next.next;
            // 第一步 虚拟节点指向2节点（第一个例子）
            pre.next = head.next;
            // 第二步 2节点指向1节点
            head.next.next = head;
            // 第三步 1节点指向临时保存的3节点
            head.next = tempNode;
            // 更新pre和head，继续循环
            pre = head;
            head = tempNode;
        }
        return dummyNode.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

19.删除链表的倒数第N个节点 题目链接
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

思路：

• 最容易想到的思路是，先计算链表的长度L，然后第 L-n+1 个节点就是要删除的节点；遍历到L-n的位置，就可以删除第L-n+1个节点了

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int len = getLength(head);
        // 虚拟头节点
        ListNode dummyNode = new ListNode(-1, head);
        ListNode pre = dummyNode;
        // 找到第len-n+1个节点的前驱节点
        for (int i = 0; i < len - n ; i++) {
            pre = pre.next;
        }
        pre.next = pre.next.next;
        return dummyNode.next;
    }
    private int getLength(ListNode head) {
        if (head == null) {
            return 0;
        }
        ListNode cur = head;
        int result = 0;
        while(cur != null) {
            result++;
            cur = cur.next;
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

• 前后指针确定删除节点位置
  创建指向head的虚拟头结点dummyNode，前指针指向dummyNode，后指针指向前指针移动n+1步后的位置，然后俩指针同时每次步进1，直到后指针指向null，此时前指针指向了要删除的节点的前驱节点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyNode = new ListNode(-1, head);
        ListNode frontNode = dummyNode;
        ListNode backNode = dummyNode;
        // 后指针backNode向后移动n+1步
        for (int i = 0; i <= n; i++) {
            backNode = backNode.next;
        }
        // 前后指针同时移动，直到backNode指向null，此时front指针指向了要删除的节点的前驱节点
        while (backNode != null) {
            frontNode = frontNode.next;
            backNode = backNode.next;
        }
        // 开始删除节点
        frontNode.next = frontNode.next.next;
        return dummyNode.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

160.链表相交
题目链接 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
思路：

• 最容易想到的思路是，利用哈希集合的contains方法：把一个链表的节点全部存入hashSet中，然后遍历另一个链表，如果某节点存在于hashSet中，说明该节点就是相交节点

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> setA = new HashSet<>();
        ListNode cur = headA;
        while (cur != null) {
            setA.add(cur);
            cur = cur.next;
        }
        cur =  headB;
        while (cur != null) {
            if (setA.contains(cur)) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

142.环形链表II
题目链接
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

不允许修改 链表。

思路：推导过程较复杂，先记着思路
第一步：快慢指针指针指向头节点，慢指针步进1，快指针步进2，如果相遇则链表有环，否则不然；
第二部：有环后，一个指针指向头节点，一个指针指向头节点，一个指针指向第一步的相遇点，然后俩指针同时步进1，新的相遇点即为入环点；

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // fast指向无环链表最后一个节点或者fast指向null结束
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            // 相遇有环
            if (slow == fast) {
                ListNode fisrtNode = head;
                ListNode meetingNode = slow;
                while (fisrtNode != meetingNode) {
                    fisrtNode = fisrtNode.next;
                    meetingNode = meetingNode.next;
                }
                return meetingNode;
            }
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22