链表

分类:

  • 单链表
  • 双链表

特点:

  • 链表对按索引(下标)查找不友好,时间复杂度O(n)
  • 对插入友好,O(1)

遍历:

  • 迭代:next 指针的存在使得链表可以使用 while 循环进行迭代
  • 递归:链表的结构决定了它可以递归,比如打印当前链表:
public static void print(ListNode head) {
    if (head == null) {
        return;
    }
    
    System.out.println(head.val);
    print(head.next); // 递归
}

技巧:

  • 双指针技巧:一快一慢、一先一后
  • 哨兵:设置一个伪节点作为 head 的 prev,或者作为 tail 的 next,以便在循环中一致地处理每一个节点

本节目前涵盖了 LeetCode 141,142,160,19,206,203,328,234,21,2,430,138,61 题,部分题目的解法还要参考 LeetCode 上的一些题解进行进一步的理解、优化;


环形链表-双指针技巧

1. 判定链表中是否存在环-141

双指针技巧

问题:如何判定链表中有环?

  • 用哈希表,已经存在相同的 key,就表示出现了环
  • 双指针技巧:如果出现了环,那么快的指针最终一定会与慢指针相遇;

双指针技巧实现:

  • 慢指针每次走1步,快指针每次走2步,可知,假设存在环,那么在慢指针还没开始走第二圈的时候,快指针已经追上了慢指针(极端情况是链表首尾相连,此时,刚好在慢指针走完第一圈时,快指针走完了第二圈,相遇点=环的入口)
  • 每次快指针多走一步,当快慢指针相遇时,快指针已经绕环走了 S 圈(S为环的长度)
public class Solution {
    public boolean hasCycle(ListNode head) {
        boolean res = false;

        ListNode slow = head;
        ListNode fast = head;
        while (slow != null && fast != null) {
            slow = slow.next;
            fast = fast.next;
            if (slow == null || fast == null) {
                break;
            }

            fast = fast.next; // fast 多走一步
            if (slow == fast) {
                res = true;
                break;
            }
        }

        return res;
    }
}

2. 找到环的入口-142

思路:

  1. 用哈希表存,找到第一个重复的节点
  2. 用快慢指针法,根据规则推算,从 head 到环入口的长度=相遇点到入环点的距离 + (n-1) 圈的环长

推导公式,可知:从 head 到入环点的距离,等于 fast和slow 第一次相遇点开始到入环点的距离 + (n-1) * 环长
也就是说:当 fast 和 slow 相遇时,ptr 从 head 出发,slow 从相遇点出发,第一次相遇必然在入环点

    public static ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;
        while (slow != null) {

            if (fast.next == null || fast.next.next == null) {
                return null;
            }

            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                ListNode ptr = head;
                while (slow != ptr) {
                    slow = slow.next;
                    ptr = ptr.next;
                }

                return ptr;
            }
        }

        return null;
    }

3. 如何判断两个单向链表是否相交,如果相交,那么找出相交点-160

解法,如果相交,那么我们可以让链表 A 的尾部连接到链表 B 的 head,这样就会形成一个环。此时,判定是否相交就是找这个新链表的入环点。

 /**
     * 获取两个链表相交的点
     * 假设链表中不存在环
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        // 找到第一个链表的尾部
        ListNode cur = headA;
        while (cur.next != null) {
            cur = cur.next;
        }

        // 将第一个链表的 tail 连接到第二个链表的 head,这样就形成了环
        // 根据环形链表中的结论:从 head 出发到入环点的距离 = (n-1) * 环圈 + 相遇点-入环点
        cur.next = headB;
        // 用快慢指针法找到相遇点
        ListNode slow = headA;
        ListNode fast = headA;
        while (slow != null && fast != null) {
            if (slow.next == null || fast.next == null || fast.next.next == null) {
                break;
            }
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                ListNode ptr = headA;
                // 从相遇点出发
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }

                cur.next = null;
                return ptr;
            }
        }

        cur.next = null;

        return null;
    }

4. 删除倒数第 n 个节点-19

在 O(n) 时间复杂度内删除倒数第 n 个节点

用快慢指针法,快指针先走 n 步,然后快慢指针一起走,当快指针到达链表尾部时,删掉慢指针所在节点;

 /**
     * 两个指针,fast 先走 n 步,然后 slow 出发,当 fast.next == null 时,删掉 slow
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }

        // 初始化 fast 和 head 两个指针,让 fast 先走 n 步
        ListNode fast = head;
        ListNode slow = head;
        for (int i = 0; i < n - 1; i++) {
            if (fast.next == null) {
                return null;
            }

            fast = fast.next;
        }

        // 上面走了 n - 1 步,再走一步
        if (fast.next == null) {
            // 这一步表示达到末尾了,也就是要删除第一个元素
            return head.next;
        }

        fast = fast.next;

        // fast 和 slow 一起走,直到 fast 达到链表尾部,此时,slow 位置就是要删除的节点
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        if (slow.next != null) {
            slow.next = slow.next.next;
        }
        return head;
    }

经典问题

1. 反转链表-206

  • 迭代:一次遍历,从 head 开始,顺序迭代,每次都将 head 的下一个节点放到链表头部,时间复杂度 O(n),空间复杂度 O(1)
  • 递归:每次递归,将第一个节点放到最后;递归需要堆栈,空间复杂度变为 O(n);(所以对于这一题,还是迭代的方式很简洁)

迭代

public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 每次都将原来的 head 的下一个节点放到第一个节点
        ListNode lastHead = head;
        while (head.next != null) {
            ListNode newHead = head.next;
            head.next = head.next.next;
            newHead.next = lastHead;
            lastHead = newHead;
        }

        return lastHead;
    }

递归

    public static ListNode reverse(ListNode head) {
        if (head.next == null) {
            return head;
        }

        ListNode last = reverse(head.next);
        head.next.next = head; // 把 head 放到 last 的尾部,这样 head 就完成了反转
        head.next = null;
        return last;
    }

扩展:

参考:递归反转链表的一部分

1.1 反转链表前 N 个节点

  • 迭代
  • 递归

递归实现:

public static ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            // 结束递归
            successor = head.next;
            return head;
        }

        // 反转后面的元素
        ListNode last = reverseN(head.next, n-1);
        // 将 head 放到第 N + 1 节点前面, 原来的 head.next 已经变成了 last 的tail
        head.next.next = head;
        head.next = successor;
        return last;
}

1.2 反转链表某一部分

/**
     * 反转链表 m - n 中的节点,m >= 1, n <= 链表长度
     * @return
     */
    public static ListNode reverseMN(ListNode head, int m, int n) {
        if (m == 1) {
            // 此时相当于反转链表的前 n 个节点
            return reverseN(head, n);
        }

        // 如果 m > 1,那么我们递归去反转 head.next
        head.next = reverseMN(head.next, m - 1, n - 1);
        return head;
    }    

1.3 k 个一组反转链表-25

LeetCode 25 题,难度:高
https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

思路:

  • 反转前 k 个结点,然后递归反转 x * k+1 结点开始的 k 个结点
  • 递归结束条件:直到链表剩余结点数小于 k
  • 需要准备的方法:反转前 k 个结点

2. 移除链表元素-203

移除 val 等于指定值的节点,分为两种情况:

  • 非 head 位置的元素,如果需要删除,只要 prev.next = cur.next 即可
  • head 位置的元素,如果需要删除,那么就要将 head = head.next 才行

解决办法:

  1. 首先将位于最前面的需要删除的元素删除,确保之后要删除的节点不在 head 位置,然后遍历一遍即可
  2. 设置一个哨兵作为伪节点,让 sentinel.next = head,从 sentinel 位置开始遍历即可

第二种的代码:

    public static ListNode removeElements(ListNode head, int val) {
        ListNode sentinel = new ListNode(-1); // 哨兵
        sentinel.next = head;

        ListNode far = sentinel;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == val) {
                far.next = cur.next;
            } else {
                far = cur;
            }
            cur = cur.next;
        }

        return sentinel.next;
    }

3. 奇偶链表-328

  • [ ] 待优化
/**
     * 奇偶转换
     * 奇数位置的节点顺序在前,偶数位置的节点顺序在后
     * @param head
     * @return
     */
    public static ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode evenHead = null;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next; // 偶数
            if (evenHead == null) {
                evenHead = cur;
            } else {
                evenHead.next = cur;
            }

            if (cur == null) {
                break;
            }
            cur = cur.next; // 奇数
        }

        return head;
    }

4. 回文链表-234

  • 方法 1: List 存储所有节点,两两对比, O(2*n) 时间复杂度,O(n) 空间复杂度
  • 方法 2:直接反转整个链表,然后分别读两个链表;时间复杂度 O(n),空间复杂度 O(n)
  • 方法 3:在方法2 基础上进行的优化 —— 用快慢指针找到中间节点,然后反转链表后半部分,然后让指针分别从 head 和 mid 出发来进行比较

方法 2,O(n) 时间复杂度的解法:

  • 用快慢指针法找到中间节点,时间 n/2
  • 反转链表后半部分, n/2
  • 用双指针分别顺序遍历前半部分和后半部分,挨个比较,最坏情况是 O(n/2)
  • 再次反转链表后半部分,以恢复链表 n/2

时间复杂度 O(n),空间复杂度 O(1)

class Solution {
     /**
     * 判定链表是否为回文字符串
     *
     * 1-2 false
     * 1-2-2-1 true
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        
        if (head == null || head.next == null) {
            return true;
        }

        ListNode mid = findMid(head);

        // 反转链表后半部分
        ListNode fast = reverseList(mid.next);

        ListNode slow = head;
        while (slow != mid.next && fast != null) {
            // 注意判定条件,在节点为偶数的情况下,slow 最后等于 mid
            // 在奇数情况下, slow.next 最后等于 mid -> 这种情况,要额外判断一下 fast 是否已经达到末尾了
            if (slow.val != fast.val) {
                reverseList(mid.next);
                return false;
            }
            slow = slow.next;
            fast = fast.next;
        }

        reverseList(mid.next);
        return true;
    }

    /**
     * 找到链表的中间节点
     * 1-2-3-4 => 2
     * 1-2-3 => 2
     * @param head
     * @return
     */
     static ListNode findMid(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            if (fast != null) {
                slow = slow.next;
            }
        }
        return slow;
    }

    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 1-2-3-4-5 -> 5-4-3-2-1
        // 每次都将原来的 head 的下一个节点放到第一个节点
        ListNode lastHead = head;
        while (head.next != null) {
            ListNode newHead = head.next;
            head.next = head.next.next;
            newHead.next = lastHead;
            lastHead = newHead;
        }

        return lastHead;
    }
}

扩展问题

1. 合并两个有序链表-21

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 思路:都插入到新链表中,这样只需要遍历 O(n)

        ListNode sentinel = new ListNode(-1);
        ListNode cur = sentinel;
        ListNode a = l1;
        ListNode b = l2;
        while (true) {

            if (a == null && b == null) {
                break;
            } else {
                if (a == null) {
                    cur.next = b;
                    b = b.next;
                } else if (b == null) {
                    cur.next = a;
                    a = a.next;
                } else {
                    if (a.val <= b.val) {
                        cur.next = a;
                        a = a.next;
                    } else {
                        cur.next = b;
                        b = b.next;
                    }
                }
                cur = cur.next;
            }
        }

        return sentinel.next;
    }

2. 两数相加-2

题目:给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。

请你将两个数相加,并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode sentinel = new ListNode(-1);
        ListNode aCur = l1;
        ListNode bCur = l2;
        ListNode rCur = sentinel;
        int carryNum = 0;
        int thisSum = 0;
        while (true) {
            if (aCur == null && bCur == null) {
                if (carryNum > 0) {
                    rCur.next = new ListNode(carryNum);
                }
                break;
            }

            thisSum = carryNum;
            if (aCur == null) {
                thisSum += bCur.val;
                bCur = bCur.next;
            } else if (bCur == null) {
                thisSum += aCur.val;
                aCur = aCur.next;
            } else {
                thisSum += (aCur.val + bCur.val);
                aCur = aCur.next;
                bCur = bCur.next;
            }

            carryNum = 0;
            if (thisSum >= 10) {
                thisSum = thisSum - 10;
                carryNum = 1;
            }
            rCur.next = new ListNode(thisSum);
            rCur = rCur.next;
        }

        return sentinel.next;
    }

3. 扁平化多级双向链表-430

第一直觉:递归
为什么选择递归呢,因为每一个节点都可能有 child,而每一个 child 也都可能有自己的 child,子子孙孙无穷尽也。显然这里用递归是非常合适的。

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/

class Solution {
    public Node flatten(Node head) {
        if (head == null) {
            return head;
        }

        Node next = null;
        if (head.child == null) {
            if (head.next != null) {
                next = flatten(head.next);
            }
        } else {
            Node oldNext = head.next;
            next = flatten(head.child);

            if (oldNext != null) {
                Node newTail = next;
                while (newTail.next != null) {
                    newTail = newTail.next;
                }

                newTail.next = oldNext;
                oldNext.prev = newTail;
            }
        }

        head.child = null;
        head.next = next;
        if (next != null) {
            next.prev = head;
        }

        return head;
    }
}

4. 复制带随机指针的链表-138

题目描述:链表中每个节点都有一个 random 指针,指向任意的其他节点或空节点。要求实现一个函数,实现链表的深拷贝。

思路:

  • 用一个 map 存储原来节点和对应的拷贝节点,第一次遍历链表拷贝 val,第二次遍历链表拷贝 next 和 random
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node, Node> copyMap = new HashMap<>();

        // copy val
        Node cur = head;
        while (cur != null) {
            Node copy = new Node(cur.val);
            copyMap.put(cur, copy);
            cur = cur.next;
        }

        // copy next and random
        cur = head;
        while (cur != null) {
            Node copy = copyMap.get(cur);
            copy.next = copyMap.get(cur.next);
            copy.random = copyMap.get(cur.random);

            cur = cur.next;
        }

        return copyMap.getOrDefault(head, null);
    }
}

5. 旋转链表-61

解法:形成环,然后找到新的 head 并断开环

public ListNode rotateRight(ListNode head, int k) {
        if (k <= 0 || head == null) {
            return head;
        }
        int size = 0;
        ListNode tail = null;
        ListNode cur = head;
        while (cur != null) {
            size++;
            if (cur.next == null) {
                tail = cur;
            }
            cur = cur.next;
        }

        // 变成环
        tail.next = head;

        // 在合适的位置断开环
        int i = 0;
        k = k % size; // 取余数
        while (i < size - k) {
            tail = tail.next;
            i++;
        }

        ListNode newHead = tail.next;
        tail.next = null;
        return newHead;
    }
Last modification:February 23rd, 2021 at 10:17 pm
请作者喝杯肥宅快乐水吧!