Day7-2021.1.15 剑指offer的七道链表题目的整理。06.从尾到头打印链表+18 .删除链表的节点+22 .链表中倒数第k个节点+ 24.反转链表+25.合并两个排序的链表+35.复杂链

Day7-2021.1.15 剑指offer的七道链表题目的整理。06.从尾到头打印链表+18 .删除链表的节点+22 .链表中倒数第k个节点+ 24.反转链表+25.合并两个排序的链表+35.复杂链表的复制+52.两个链表的第一个公共节点

LeetCode题解汇总

当前已更新下面的剑指offer的七道链表题目：
剑指 Offer 06.从尾到头打印链表
剑指 Offer 18 .删除链表的节点
剑指 Offer 22 .链表中倒数第k个节点
剑指 Offer 24 .反转链表
剑指 Offer 25 .合并两个排序的链表
剑指 Offer 35 .复杂链表的复制
剑指 Offer 52 .两个链表的第一个公共节点

自己写的程序的规格结构，如下图：

剑指 Offer 06.从尾到头打印链表

思考：利用栈“先进后出”的性质。遍历链表，存储结点值。遍历输出栈值。业务代码还是很容易写的。

引申可见 剑指 Offer 24 .反转链表

为了在IDEA上方便调试，需要实现“nums2ListNode”，即数组转链表的业务代码。

private static ListNode nums2ListNode(int[] nums) {
    // 1.首先先去创建头结点
    ListNode head = new ListNode(nums[0]);
    // 2.创建结点 node 去遍历数组元素
    ListNode node = head;
    // 3.从数组的第2个元素依次遍历
    for (int i = 1; i < nums.length; i++) {
        // 4.创建临时结点
        ListNode temp = new ListNode(nums[i]);
        node.next = temp;
        // 更新 node 节点
        node = temp;
    }
    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

为了在IDEA上方便调试，需要实现“printListNode”，即链表内容打印的业务代码。

private static void printListNode(ListNode head) {
    StringBuffer res = new StringBuffer();
    while (head.next != null) {
        res.append(head.val + "->");
        head = head.next;
    }
    res.append(head.val);
    System.out.println(res);
}
1
2
3
4
5
6
7
8
9

完整代码：

ArrayList如何转换为int[]数组 https://blog.csdn.net/huanghanqian/article/details/73920439
这个是java8的特性
int[] res = list.stream().mapToInt(Integer::intValue).toArray();

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

public class Offer06 {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 3, 2};
        ListNode head = nums2ListNode(nums);
        printListNode(head);
        System.out.println(reversePrint(head));
    }

    private static void printListNode(ListNode head) {
        StringBuffer res = new StringBuffer();
        while (head.next != null) {
            res.append(head.val + "->");
            head = head.next;
        }
        res.append(head.val);
        System.out.println(res);
    }

    private static ListNode nums2ListNode(int[] nums) {
        // 1.首先先去创建头结点
        ListNode head = new ListNode(nums[0]);
        // 2.创建结点 node 去遍历数组元素
        ListNode node = head;
        // 3.从数组的第2个元素依次遍历
        for (int i = 1; i < nums.length; i++) {
            // 4.创建临时结点
            ListNode temp = new ListNode(nums[i]);
            node.next = temp;
            // 更新 node 节点
            node = temp;
        }
        return head;
    }

    public static int[] reversePrint(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();
        while (head != null) {
            stack.push(head.val);
            head = head.next;
        }
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        // ArrayList<Integer>如何转换为int[]数组 https://blog.csdn.net/huanghanqian/article/details/73920439
        // 这个是java8的特性
        int[] res = list.stream().mapToInt(Integer::intValue).toArray();
        return res;
    }
}

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

ListNode的代码放在外边

public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}
1
2
3
4
5
6
7
8

剑指 Offer 18 .删除链表的节点

思考：这个考虑可能删除头结点，尾节点，等情况，需要采用“虚拟头结点”+“快慢指针”的操作。

要删除一个节点，那么该节点的前一个节点指向该节点的后一个节点，并将该节点的next指向null，则实现了删除指定节点的操作。

import java.util.ArrayList;
import java.util.Stack;

public class Offer18 {
    public static void main(String[] args) {
        int[] nums = new int[]{4, 5, 1, 9};
        ListNode head = nums2ListNode(nums);
        printListNode(head);
        ListNode resHead = deleteNode(head, 5);
        printListNode(resHead);
    }

    private static void printListNode(ListNode head) {
        StringBuffer res = new StringBuffer();
        while (head.next != null) {
            res.append(head.val + "->");
            head = head.next;
        }
        res.append(head.val);
        System.out.println(res);
    }

    private static ListNode nums2ListNode(int[] nums) {
        // 1.首先先去创建头结点
        ListNode head = new ListNode(nums[0]);
        // 2.创建结点 node 去遍历数组元素
        ListNode node = head;
        // 3.从数组的第2个元素依次遍历
        for (int i = 1; i < nums.length; i++) {
            // 4.创建临时结点
            ListNode temp = new ListNode(nums[i]);
            node.next = temp;
            // 更新 node 节点
            node = temp;
        }
        return head;
    }

    public static ListNode deleteNode(ListNode head, int val) {
        // 1.创建虚拟头结点
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        // 2.创建快慢指针
        ListNode fast = dummyNode.next;
        ListNode slow = dummyNode;
        // 3.遍历查找需要删除的节点
        while (fast != null) {
            // 一个要删除的节点的值
            if (fast.val == val) {
                // 该节点的前一个节点指向该节点的后一个节点
                slow.next = fast.next;
                // 将该节点的next指向null。这里好像是加不加都可以。
                fast.next = null;
                break;
            }
            // 更新节点
            slow = slow.next;
            fast = fast.next;
        }
        // 这里是考虑到头结点就是要删除的节点的情况
        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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

剑指 Offer 22 .链表中倒数第k个节点

思考：“快慢指针”，先让快指针走k步，然后快慢指针同时向前走，当快指针到达链表末尾，慢指针指向了目标节点。

public class Offer22 {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4, 5};
        ListNode head = nums2ListNode(nums);
        printListNode(head);
        ListNode resHead = getKthFromEnd(head, 2);
        printListNode(resHead);
    }

    private static void printListNode(ListNode head) {
        StringBuffer res = new StringBuffer();
        while (head.next != null) {
            res.append(head.val + "->");
            head = head.next;
        }
        res.append(head.val);
        System.out.println(res);
    }

    private static ListNode nums2ListNode(int[] nums) {
        // 1.首先先去创建头结点
        ListNode head = new ListNode(nums[0]);
        // 2.创建结点 node 去遍历数组元素
        ListNode node = head;
        // 3.从数组的第2个元素依次遍历
        for (int i = 1; i < nums.length; i++) {
            // 4.创建临时结点
            ListNode temp = new ListNode(nums[i]);
            node.next = temp;
            // 更新 node 节点
            node = temp;
        }
        return head;
    }

    public static ListNode getKthFromEnd(ListNode head, int k) {
        // 1.创建快慢指针
        ListNode fast = head;
        ListNode slow = head;
        // 2.先让快指针走k步
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
        // 3.然后快慢指针同时向前走，当快指针到达链表末尾，慢指针指向了目标节点。
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

剑指 Offer 24 .反转链表

思考：“双指针”，1.保存cur的下一个节点。2.转向，后节点指向前节点。3.更新节点，两个节点都向前走一步。这个做题步骤特别统一。不能采用“虚拟头结点”，pre应该直接设置为null。

public class Offer24 {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4, 5};
        ListNode head = nums2ListNode(nums);
        printListNode(head);
        ListNode resHead = reverseList(head);
        printListNode(resHead);
    }

    private static void printListNode(ListNode head) {
        StringBuffer res = new StringBuffer();
        while (head.next != null) {
            res.append(head.val + "->");
            head = head.next;
        }
        res.append(head.val);
        System.out.println(res);
    }

    private static ListNode nums2ListNode(int[] nums) {
        // 1.首先先去创建头结点
        ListNode head = new ListNode(nums[0]);
        // 2.创建结点 node 去遍历数组元素
        ListNode node = head;
        // 3.从数组的第2个元素依次遍历
        for (int i = 1; i < nums.length; i++) {
            // 4.创建临时结点
            ListNode temp = new ListNode(nums[i]);
            node.next = temp;
            // 更新 node 节点
            node = temp;
        }
        return head;
    }

    public static ListNode reverseList(ListNode head) {
        // 1.创建双指针
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            // 2.保存cur的下一个节点
            ListNode nextNode = cur.next;
            // 3.转向，后节点指向前节点。
            cur.next = pre;
            // 4.更新节点，两个节点都向前走一步。
            pre = cur;
            cur = nextNode;
        }
        // 经过while,cur指向为null，pre指向尾节点。
        return pre;
    }
}
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

剑指 Offer 25 .合并两个排序的链表

思考：新建一个链表，比较链表l1和l2的值，依次将元素添加到新链表中。

【力扣官方将这个题目归为了分治算法】

先去写 newNode = newNode.next;是不行的，newNode.next现在是null，必须先去newNode.next=l1，这样给newNode.next赋值，才能更新newNode节点：newNode = newNode.next;

public class Offer25 {
    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 2, 4};
        int[] nums2 = new int[]{1, 3, 4};
        ListNode l1 = nums2ListNode(nums1);
        ListNode l2 = nums2ListNode(nums2);
        printListNode(l1);
        printListNode(l2);
        ListNode resHead = mergeTwoLists(l1, l2);
        printListNode(resHead);
    }

    private static void printListNode(ListNode head) {
        StringBuffer res = new StringBuffer();
        while (head.next != null) {
            res.append(head.val + "->");
            head = head.next;
        }
        res.append(head.val);
        System.out.println(res);
    }

    private static ListNode nums2ListNode(int[] nums) {
        // 1.首先先去创建头结点
        ListNode head = new ListNode(nums[0]);
        // 2.创建结点 node 去遍历数组元素
        ListNode node = head;
        // 3.从数组的第2个元素依次遍历
        for (int i = 1; i < nums.length; i++) {
            // 4.创建临时结点
            ListNode temp = new ListNode(nums[i]);
            node.next = temp;
            // 更新 node 节点
            node = temp;
        }
        return head;
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyNode = new ListNode(0);
        ListNode newNode = dummyNode;
        // 循环结束条件 && 使得l1,l2其中一个为空时，则跳出while循环。
        while (l1 != null && l2 != null) {
            // 获取l1,l2中较小的节点，添加到新链表 newNode 中。
            if (l1.val < l2.val) {
                newNode.next = l1;
                // 更新链表 l1
                l1 = l1.next;
            } else {
                newNode.next = l2;
                // 更新链表 l2
                l2 = l2.next;
            }
            // 更新新链表 newNode
            newNode = newNode.next;

        }
        // l1,l2其中一个为空。
        newNode.next = l1 != null ? l1 : l2;
        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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

剑指 Offer 35 .复杂链表的复制 【需要重刷】

思考：这个题目难度明显比前面的几道题目要难一点。代码参考自1：+代码参考自2，java版本：

首先，先新建一个Node类

public class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
1
2
3
4
5
6
7
8
9
10
11

测试用例：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]。明显，自己不能用IDEA去创建测试用例。

1.哈希表方法，视频讲解如下：bilibili视频讲解：小美图解：java版 小美图解剑指offer35题 复杂链表的复制 算法刷题。这个视频多看几次，加深理解。

首先利用 HashMap 来一个不用思考的代码。
遍历第一遍链表，我们不考虑链表之间的相互关系，仅仅生成所有节点，然后把它存到 HashMap 中，val 作为 key，Node 作为 value。
遍历第二遍链表，将之前生成的节点取出来，更新它们的 next 和 random 指针。

import java.util.HashMap;

public class Offer35 {
    public static void main(String[] args) {
        System.out.println(" 测试用例：`head = [[7,null],[13,0],[11,4],[10,2],[1,0]]`。");
        System.out.println("明显，自己不能用IDEA去创建测试用例。");
    }

    public Node copyRandomList(Node head) {
        // 给定的链表为空（空指针），因此返回 null。
        if (head == null) {
            return null;
        }
        // 新建 HashMap 遍历存储 链表的节点+节点值。
        // 键值对都是Node类型。
        HashMap<Node, Node> map = new HashMap<>();
        Node cur = head;
        // 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        while (cur != null) {
            Node val = new Node(cur.val);
            map.put(cur, val);
            cur = cur.next;
        }
        // 遍历完成后返回到头结点
        cur = head;
        // 构建新链表的 next 和 random 指向
        while (cur != null) {
            if (cur.next != null) {
                map.get(cur).next = map.get(cur.next);
            }
            if (cur.random != null) {
                map.get(cur).random = map.get(cur.random);
            }
            cur = cur.next;
        }
        // 返回新链表的头节点
        return map.get(head);
    }
}
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
34
35
36
37
38
39

2.bilibili视频讲解【采用了递归的方法。可以先不看这个解法。感觉看了下面的代码，更加困惑了。】来自 子烁爱学习

import java.util.HashMap;

public class Offer35_bilibili {
    public static void main(String[] args) {
        System.out.println(" 测试用例：`head = [[7,null],[13,0],[11,4],[10,2],[1,0]]`。");
        System.out.println("明显，自己不能用IDEA去创建测试用例。");
    }

    HashMap<Node, Node> map = new HashMap<>();

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        if (map.containsKey(head)) {
            return map.get(head);
        }
        Node tempNode = new Node(head.val);
        map.put(head, tempNode);
        // 这里有一个递归调用哦。
        tempNode.next = copyRandomList(head.next);
        // 这里有一个递归调用哦。上面的递归完成，这里才会执行。
        tempNode.random = copyRandomList(head.random);
        return tempNode;
    }
} 
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

剑指 Offer 52 .两个链表的第一个公共节点 【需要重刷】

思考：一种方法是：用A的一个节点，去比较B的所有节点。复杂度是O(n^2)。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode copyheadB=headB;
        while(headA!=null){
            while(headB!=null){
                if(headA==headB){
                    return headA;
                }else{
                    headB=headB.next;
                }
            }
            headA=headA.next;
            headB=copyheadB;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

思考：另一个巧妙的思路是：我们使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。这样，当它们相遇时，所指向的结点就是第一个公共结点。

假如两个没有交点，两个链表一直交换不会死循环吗？

答：如果没有重合部分，那么 a 和 b 在某一时间点 一定会同时走到 null，从而结束循环。System.out.println(null==null);// 输出为 true while (PA != PB) 在这里会跳出while循环，到达下一步 return PA，也就是 return null。

如果有重合部分，分两种情况。

长度相同的话， a 和 b 一定是同时到达相遇点，然后返回。
长度不同的话，较短的链表先到达结尾，然后指针转向较长的链表。此刻，较长的链表继续向末尾走，多走的距离刚好就是最开始介绍的解法，链表的长度差，走完之后指针转向较短的链表。然后继续走的话，相遇的位置就刚好是相遇点了。

视频讲解：小美图解剑指Offer 52题 两个链表的第一个公共节点 java版本

headA：4->1->8->4->5
headB：5->0->1->8->4->5

headAB：4->1->8->4->5->5->0->1->8->4->5

headBA：5->0->1->8->4->5->4->1->8->4->5

测试用例如上图，但是我在IDEA上不会设置测试用例，最终代码如下。代码参考自1：+代码参考自2：

public class Offer52 {
    public static void main(String[] args) {
        int[] nums1 = new int[]{4, 1, 8, 4, 5};
        int[] nums2 = new int[]{5, 0, 1, 8, 4, 5};
        ListNode headA = nums2ListNode(nums1);
        ListNode headB = nums2ListNode(nums2);
        printListNode(headA);
        printListNode(headB);
        ListNode resHead = getIntersectionNode(headA, headB);
        printListNode(resHead);
    }

    private static void printListNode(ListNode head) {
        StringBuffer res = new StringBuffer();
        while (head.next != null) {
            res.append(head.val + "->");
            head = head.next;
        }
        res.append(head.val);
        System.out.println(res);
    }

    private static ListNode nums2ListNode(int[] nums) {
        // 1.首先先去创建头结点
        ListNode head = new ListNode(nums[0]);
        // 2.创建结点 node 去遍历数组元素
        ListNode node = head;
        // 3.从数组的第2个元素依次遍历
        for (int i = 1; i < nums.length; i++) {
            // 4.创建临时结点
            ListNode temp = new ListNode(nums[i]);
            node.next = temp;
            // 更新 node 节点
            node = temp;
        }
        return head;
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode PA = headA;
        ListNode PB = headB;
        while (PA != PB) {
            PA = (PA == null ? headB : PA.next);
            PB = (PB == null ? headA : PB.next);
        }
        return PA;
    }
}
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

今日语录：
这世上的爱，原本有千万种模样。他们的生活中，虽然没有甜言蜜语、海誓山盟，却有无数个庸常日子里的点滴温暖，和那些柴米油盐里的守望相助。因为懂得，所以慈悲。