《剑指Offer》--- 数据结构の链表篇

目录

面试题06：从尾到头打印链表

面试题18：删除链表的节点

面试题22：链表中倒数第k个结点

面试题23：链表中环的入口结点

面试题24：反转链表

面试题25：合并两个排序的链表

面试题35：复杂链表的复制

面试题52：两个链表的第一个公共节点

---

✨知识回顾✨

小伙伴还记得 head，node，val，prev 和 next，以及链表的一些基础 *** 作嘛？如果忘记了，那就一起来回顾一下吧🌞

👉数据结构---链表

面试题06：从尾到头打印链表

🌸题目：

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）

🍀示例：

输入：head = [2,5,7]

输出：[7，5，2]

🌺链接：剑指 Offer 06

方法一：题目要求用数组返回，我们只需要创建一个链表节点数大小的数组，然后在数组中从后往前输入链表的结点打印即可。

public class Question {
    public int[] reversePrint(ListNode head){
        ListNode node = head;
        int count = 0;
        while(node != null){
            count++;
            node = node .next;
        }
        int[] nums = new int[count];
        node = head;
        for(int i = count - 1;i >= 0;i--){
            nums[i] = node.val;
            node = node.next;
        }
        return nums;
    }
}

方法二：栈的特点是后进先出，即最后压入栈的元素最先d出。

考虑到栈的这一特点，使用栈将链表元素顺序倒置。

从链表的头节点开始，依次将每个节点压入栈内，然后依次d出栈内的元素并存储到数组中。

class Solution {
    public int[] reversePrint(ListNode head) {
        Stack stack = new Stack();
        ListNode node = head;
        while (node != null) {
            stack.push(node);
            node = node.next;
        }
        int size = stack.size();
        int[] print = new int[size];
        for (int i = 0; i < size; i++) {
            print[i] = stack.pop().val;
        }
        return print;
    }
}

面试题18：删除链表的节点

🌸题目：

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点

🍀示例：

输入：head = [5，2，3，6，4]，val = 6

输出：[5，2，3，4]

🌺链接：剑指 Offer 18

方法一

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head.val == val){
            return head.next;
        } 
        ListNode pre = head, cur = head.next;
        while(cur != null && cur.val != val) {
            pre = cur;
            cur = cur.next;
        }
        if(cur != null){
            pre.next = cur.next;
        } 
        return head;
    }
}

方法二：递归

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        if (head.val == val) {
            return head.next;
        } else {
            head.next = deleteNode(head.next, val);
        }
        return head;
    }
}

面试题22：链表中倒数第k个结点

🌸题目：

输入一个链表，输出该链表中倒数第k个节点。

为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。

这个链表的倒数第 3 个节点是值为 4 的节点。

🍀示例：

给定链表：1 -> 2 -> 3 -> 4 -> 5 , k = 2

返回链表：4 -> 5

🌺链接：剑指 Offer 22

方法一：顺序查找，假设当前链表的长度为 nn，则我们知道链表的倒数第 k 个节点即为正数第 n - k 个节点，此时我们只需要顺序遍历到链表的第 n - k 个节点即为倒数第 k 个节点。

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        int n = 0;
        ListNode node = null;
        for (node = head; node != null; node = node.next) {
            n++;
        }
        for (node = head; n > k; n--) {
            node = node.next;
        }
        return node;
    }
}

方法二：我们将第一个指针 fast 指向链表的第 k+1 个节点，第二个指针 slow 指向链表的第一个节点，此时指针 fast 与 slow 二者之间刚好间隔 k 个节点。

此时两个指针同步向后走，当第一个指针 fast 走到链表的尾部空节点时，则此时 slow 指针刚好指向链表的倒数第k个节点。

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode prev = head;
        ListNode cur = head;
        for(int i = 0; i < k - 1;i++){
            cur = cur.next;
        }
        while(cur.next != null){
            prev = prev.next;
            cur = cur.next;
        }
        return prev;
    }
}

面试题23：链表中环的入口结点

🌸题目：

给定一个链表，返回链表开始入环的第一个节点。

从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。

如果链表无环，则返回 null

🌺链接：剑指 Offer 23

方法一：遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。

借助哈希表可以很方便地实现。

public class Question{
   public ListNode detectCycle(ListNode head){
       Set set = new HashSet();
       ListNode node = head;
       while(node != null){
          if(set.contains(node)){
              return node;
          } else {
              set.add(node);
          }
          node = node.next;
       }
       return null;
   }
}

方法二：使用两个指针，fast 与slow。

它们起始都位于链表的头部。

随后，slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置。

如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

面试题24：反转链表

🌸题目：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

🌺链接：剑指 Offer 24

public class Question{
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode prev = null;

        while(cur != null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

面试题25：合并两个排序的链表

🌸题目：

将两个升序链表合并为一个新的 升序 链表并返回。

新链表是通过拼接给定的两个链表的所有节点组成的。

🍀示例:

输入：l1 = [1 , 2 , 3 , 5] , l2 = [2 , 4 , 6]

输出:  l = [1 , 2 , 2 , 3 , 4 , 5 , 6]

🌺链接: 剑指 Offer 25

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode cur1 = list1;
        ListNode cur2 = list2;

        ListNode newHead = new ListNode(0);
        ListNode newLast = newHead;

        while(cur1 != null && cur2 != null){
            if(cur1.val <= cur2.val){
                newLast.next = cur1;
                cur1 = cur1.next;
            } else {
                newLast.next = cur2;
                cur2 = cur2.next;
            }
            newLast = newLast.next;
        }

        if(cur1 != null){
            newLast.next = cur1;
        } else {
            newLast.next = cur2;
        }
        return newHead.next;
    }
}

面试题35：复杂链表的复制

🌸题目：

请实现 copyRandomList 函数，复制一个复杂链表。

在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

🍀示例：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

🌺链接：剑指 Offer 35

对于当前节点，我们首先要进行拷贝，然后我们进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝，拷贝完成后将创建的新节点的指针返回，即可完成当前节点的两指针的赋值。

class Question {
    public Node copyRandomList(Node head) {
        Map cachedNode = new HashMap();
        if (head == null) {
            return null;
        }
        if (!cachedNode.containsKey(head)) {
            Node headNew = new Node(head.val);
            cachedNode.put(head, headNew);
            headNew.next = copyRandomList(head.next);
            headNew.random = copyRandomList(head.random);
        }
        return cachedNode.get(head);
    }
}

面试题52：两个链表的第一个公共节点

🌸题目：

输入两个链表，找出它们的第一个公共节点。

🍀示例：

输入：headA = [1,2,5,3,7]   headB = [4,6,5,3,7]

输出: 5

🌺链接：剑指 Offer 52

方法一：首先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。

然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set visited = new HashSet();
        ListNode temp = headA;
        while (temp != null) {
            visited.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while (temp != null) {
            if (visited.contains(temp)) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
}

方法二：只有当链表 headA 和 headB 都不为空时，两个链表才可能相交。

因此首先判断链表 headA 和 headB 是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 null。

当链表 headA 和 headB 都不为空时，创建两个指针 pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}