当前位置:   article > 正文

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

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去创建测试用例。

image-20210115103628209

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

image-20210115094510717

测试用例如上图,但是我在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

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/758886
推荐阅读
相关标签
  

闽ICP备14008679号