算法训练营（day04）

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

题目链接：https://leetcode.cn/problems/swap-nodes-in-pairs/description/

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

解题思路

思路一：虚拟头节点

解题过程：

  1. 定义一个虚拟头节点dum，令cur = dum

  2. 定义循环条件为 cur.next != null && cur.next.next != null

  3. 定义 tmp = head.next.next ，保留第三个节点的值

  4. 开始进行两两交换(eg: dum -> 1 ->2 -> 3…)

    • 令 cur 的 next 指向 head.next (dum -> 2)
    • 令 head.next 的 next 指向 head(2 -> 1)
    • 令 head 的 next 指向 tmp(1 -> 3)
    • 以上三步完成两两交换(dum -> 2 -> 1 -> 3)

  5. 向后移动,两两交换(eg: -> 3 -> 4 …)

    • 令cur 指向需要进行两两交换的节点之前的节点 cur = head (cur = 1)
    • 令 head 指向需要进行两两交换的节点的 首节点 head = head.next (head = 3)

  6. 结束循环后，返回 dum.next ，表示返回的是实际的从头(head)遍历

思路二：递归

解题过程：

  1. 先判断 head 够不够两个，不够直接判空

  2. 定义 next = head.next (next = 2)

  3. 定义一个 newNode ，取 next.next(= 3) 对链表进行递归 (newNode = 4)

  4. 补全连接关系

    • next.next = head (2 -> 1)
    • head.next = newNode (1 -> 4)

  5. 返回交换结果 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
25
26
27
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dum = new ListNode(0);
        dum.next = head;
        ListNode cur = dum;
        while(cur.next != null && cur.next.next != null){
            ListNode tmp = head.next.next;  //3
            cur.next = head.next;           //dum -> 2
            head.next.next = head;          //2 -> 1
            head.next = tmp;                //1 -> 3

            cur = head;
            head = head.next;
        }
        return dum.next;
    }
}

解法二：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode next = head.next;                  //2
        ListNode newNode = swapPairs(next.next);    //4
        next.next = head;                           //2 -> 1
        head.next = newNode;                        //1 -> 4
        return next;
    }
}

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

题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

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

解题思路

解题过程：

  1. 定义一个虚拟头节点dum，dum.next = head
  2. 定义快慢指针 fast， slow
  3. 让 fast 先走 n 步 fast = fast.next
  4. 再让fast 和 slow 同时步进
    • fast = fast.next
    • slow = slow.next
  5. 当 fast.next = null 时，说明 slow.next 即为需要删除的节点
    • 删除节点仅需令 slow.next = slow.next.next
  6. 返回 dum.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
25
26
27
28
29
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dum = new ListNode(0);
        dum.next = head;

        ListNode fast = dum;
        ListNode slow = dum;
        while(n-- > 0){
            fast = fast.next;
        }
        
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dum.next;
    }
}

面试题02.07.链表相交

题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/

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

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

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

解题思路

本题参考K神解法： https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/solutions/1190240/mian-shi-ti-0207-lian-biao-xiang-jiao-sh-b8hn/

解题过程：

  1. 设「第一个公共节点」为 node ，「链表 headA」的节点数量为 a ，「链表 headB」的节点数量为 b ，「两链表的公共尾部」的节点数量为 c ，则有：

    • 头节点 headA 到 node 前，共有 a−c 个节点；
    • 头节点 headB 到 node 前，共有 b−c 个节点；

  2. 指针 A 先遍历完链表 headA ，再开始遍历链表headB ，当走到 node 时，共走步数为：a+(b−c)

  3. 同理，指针 B 先遍历完链表 headB ，再开始遍历链表headA ，当走到 node 时，共走步数为：b+(a−c)

  4. 当指针 A , B 重合时，即：a+(b−c)=b+(a−c)

    • 有 公共尾部 (即 c>0 ) ：指针 A , B 同时指向「第一个公共节点」node
    • 无 公共尾部 (即 c=0 ) ：指针 A , B 同时指向 null

  5. 无论什么结果，返回指针的值即可

详细代码

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null){
            return null;
        }
        ListNode a = headA;
        ListNode b = headB;

        while (a != b){
            a = a==null ? headB : a.next;
            b = b==null ? headA : b.next;
        }
        return a;
    }
}

142.环形链表II

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

解题思路

解题过程：

  1. 判断 head 的长度，如果小于2，不可能有环， 直接判空

  2. 定义快慢指针 fast， slow

  3. 定义循环条件 fast != null && fast.next != null

  4. 令 fast = fast.next.next , slow = slow.next

  5. 判断是否有环

    • 如果有环，循环中 必有 fast = slow
    • 无环则一定会出现结束循环的状态，直接返回null即可

  6. 已判断有环后，开始找 第一个入环节点

    • 令 fast 回到头节点 head
    • 让 fast 和 slow 同时步进
      • fast = fast.next
      • slow = slow.next
    • 当再次出现 fast = slow，说明找到了 入环节点

  7. 返回 fast，即返回入环节点

详细代码

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
27
28
29
30
31
32
33
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null){
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                fast = head;
                while(fast != slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }
}