基础数据结构之链表相关的一些问题

基础数据结构之链表相关的一些问题

作者：Grey

原文地址：

博客园：基础数据结构之链表相关的一些问题

CSDN：基础数据结构之链表相关的一些问题

反转单链表

题目描述见：LeetCode 206. Reverse Linked List

思路如下

对于任何一个节点 cur 来说，记录一个前驱节点 pre (第一个节点的前驱节点是 null )

先用一个临时节点 tmp 记录 cur 的下一个节点，然后设置

cur.next = pre;pre = cur;cur = tmp;

以下是示例图

假设原始链表如下

第一个节点的反转流程如下

第二个节点的反转流程如下

最后返回 pre 节点即为反转后的节点。

代码如下

class Solution {    public ListNode reverseList(ListNode cur) {        if (cur == null || cur.next == null) {            return cur;        }        ListNode pre = null;        while (cur != null) {            ListNode tmp = cur.next;            cur.next = pre;            pre = cur;            cur = tmp;        }        return pre;    }}

时间复杂度O(N)，空间复杂度O(1)。

反转链表也可以用递归方法来实现

定义递归函数 ListNode reverse(ListNode cur)，这个递归函数的含义是

反转以 cur 为头的链表，并把反转后的头节点返回。

这个递归函数的 base case 是，只有一个节点的时候，即

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

这种情况下，直接返回当前节点即可。

接下来是普遍情况：

当前来到 cur 节点，c，d，e 已经完成了反转。

此时 cur 需要做如下操作。把 c , d, e 反转后的头节点获取到，假设为 pre ， 在上图中，pre 就是 e 节点，就是反转链表的头节点。然后再做如下操作

        cur.next.next = cur;        cur.next = null;

其中cur.next = null非常重要，只有这样，才能防止出现环。完整代码如下

class Solution {    public ListNode reverseList(ListNode cur) {        return reverse(cur);    }    // 反转cur为头的链表，并把反转后的头节点返回    public ListNode reverse(ListNode cur) {        if (cur == null || cur.next == null) {            return cur;        }        ListNode pre = reverse(cur.next);        cur.next.next = cur;        cur.next = null;        return pre;    }}

时间复杂度O(N)

空间复杂度O(N)(递归栈占用的空间)

反转双向链表

双向链表和单链表的反转类似，每个节点要多处理一次每个节点的前驱指针，

完整代码如下

package snippet;import java.util.ArrayList;import java.util.List;// 反转双向链表public class Code_0008_ReverseDoubleList {    public static class DoubleNode {        public int value;        public DoubleNode last;        public DoubleNode next;        public DoubleNode(int data) {            value = data;        }    }    public static DoubleNode reverseDoubleList(DoubleNode cur) {        DoubleNode pre = null;        while (cur != null) {            DoubleNode tmp = cur.next;            cur.next = pre;            // 处理前驱指针            cur.last = tmp;            pre = cur;            cur = tmp;        }        return pre;    }}

反转单链表一部分

题目描述见：LeetCode 92. Reverse Linked List II

本题核心依然是反转链表，只是增加了一些变量来记录需要反转链表的头位置和结尾位置，不过需要注意的是，本题的链表开始位置是从 1 开始，所以，如果m = 1 && n != 1，说明反转链表后需要返回新的头部，只要m > 1，反转链表一部分以后，返回原先的头即可。
完整代码见

class Solution {       public static ListNode reverseBetween(ListNode head, int m, int n) {        if (m == n) {            // 不变            return head;        }        ListNode startPre = null;        ListNode start = null;        ListNode end;        ListNode endAfter = null;        ListNode cur = head;        int i = 1;        while (i <= n) {            if (i == m - 1) {                startPre = cur;            } else if (i == m) {                start = cur;            } else if (i == n) {                end = cur;                if (end.next != null) {                    endAfter = end.next;                    end.next = null;                }            }            cur = cur.next;            i++;        }        i = m;        ListNode pre = null;        // 反转链表操作        while (i <= n) {            ListNode tmp = start.next;            start.next = pre;            pre = start;            start = tmp;            if (i == m) {                pre.next = endAfter;            }            i++;        }                if (m == 1 && n != 1) {            // 换头了            return pre;        }        startPre.next = pre;        // 返回原来的头节点即可。        return head;    }}

在链表中删除指定值的所有节点

题目链接：LeetCode 203. Remove Linked List Elements

主要思路就是遍历链表，找到对应值的元素，就做删除操作，对于普遍位置来说，删除操作可以按如下方式进行

不过，需要注意一个边界条件，就是：如果要删除的节点就是头节点，那么经过删除后，会面临要换头的情况。

所以在一开始的时候，需要做如下判断

        while (head != null && head.val == val) {            head = head.next;        }

即找到第一个不需要删的节点。

完整代码见

class Solution {   public static ListNode removeElements(ListNode head, int val) {        if (null == head) {            return null;        }        while (head != null && head.val == val) {            head = head.next;        }        if (head == null) {            return null;        }        ListNode c = head;        ListNode n = c.next;        while (n != null) {            if (n.val == val) {                c.next = n.next;                n = n.next;            } else {                c = n;                n = c.next;            }        }        return head;    }}

两个链表相加问题

题目链接见：LeetCode 2. Add Two Numbers

没有特别的算法，就是要注意每次相加可能会有进位的问题，所以设置一个数据结构Node，用于存每一位计算的结果，包括这一位是否有进位的情况。

    public static class Node {        // 当前值        public int v;        // 进位值（只能是0或者1）        public int n;    }

每次操作相加的方法封装为如下

    private static Node add(int v1, int v2) {        Node n = new Node();        // 5 + 7 = 12        // 则 当前值为：n.v = 2        //    进位值为：n.n = 1         n.v = (v1 + v2) % 10;        n.n = (v1 + v2) / 10;        return n;    }

还有一个边界条件，由于是从左往右依次相加，所以最右侧如果相加后超过了 9 ，那么需要在最右侧的右侧继续进一位。例如：

.....8+.....7=.....51 <--注意得到5以后，还要继续向右侧进1。

完整代码见：

class Solution {    public static class Node {        // 当前值        public int v;        // 进位值（只能是0或者1）        public int n;    }    // l1 和 l2 非空    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {        ListNode result = new ListNode();        Node start = add(l1.val, l2.val);        result.val = start.v;        l1 = l1.next;        l2 = l2.next;        ListNode c = result;        while (l1 != null && l2 != null) {            start = add(l1.val + l2.val, start.n);            c.next = new ListNode(start.v);            c = c.next;            l1 = l1.next;            l2 = l2.next;        }        while (l1 != null) {            start = add(l1.val, start.n);            c.next = new ListNode(start.v);            c = c.next;            l1 = l1.next;        }        while (l2 != null) {            start = add(l2.val, start.n);            c.next = new ListNode(start.v);            c = c.next;            l2 = l2.next;        }        if (start.n != 0) {            c.next = new ListNode(1);        }        return result;    }    private static Node add(int v1, int v2) {        Node n = new Node();        n.v = (v1 + v2) % 10;        n.n = (v1 + v2) / 10;        return n;    }}

K个节点的组内逆序调整问题

LeetCode 25. Reverse Nodes in k-Group

本题需要设计两个方法：

第一个方法ListNode getKGroupEnd(ListNode start, int k)：从链表 start 位置开始，数够 k 个位置，返回 k 个位置后的那个节点。

比如链表为：

...-> start -> b -> c -> d -> ek = 3

表示从 start 开始，数够 3 个，所以返回 c 节点

如果是下述情况

...-> start -> b -> c -> nullk = 6

由于 start 后面不够 6 个，所以返回 null。

    public static ListNode getKGroupEnd(ListNode start, int k) {        while (--k != 0 && start != null) {            start = start.next;        }        return start;    }

第二个方法void reverse(ListNode start, ListNode end)，表示反转 start 到 end 之间的链表。

例如：原链表为：

....->a->b->c->d->e....

假设start = a, end = d

经过reverse方法，会变成

...d->c->b->a->e.....

有了上述两个方法，我们可以比较方便实现原题要求，主流程如下

    public static ListNode reverseKGroup(ListNode head, int k) {        ListNode start = head;        ListNode end = getKGroupEnd(start, k);        if (end == null) {            return head;        }        // 第一组凑齐了！        head = end;        reverse(start, end);        // 上一组的结尾节点        ListNode lastEnd = start;        while (lastEnd.next != null) {            start = lastEnd.next;            end = getKGroupEnd(start, k);            if (end == null) {                return head;            }            reverse(start, end);            lastEnd.next = end;            lastEnd = start;        }        return head;    }

快慢指针问题

题目描述见：LeetCode 876. Middle of the Linked List

本题主要解决的问题是：

如果一个链表中的节点个数是奇数，则返回中点；如果个数是偶数，则返回下中点。

通常这类问题都是使用快慢指针来做，思路如下

设置一个快指针 fast，一个慢指针 slow， 快指针一次走两步，慢指针一次走一步，快指针走到结尾的时候，慢指针正好到中点位置。

完整代码见：

class Solution {    // [1,2,3,4,5] --> 3    // [1,2,3,4,5,6] --> 4    // 奇数返回中点，偶数返回下中点    public static ListNode middleNode(ListNode head) {        ListNode slow = head;        ListNode fast = head;        while (fast != null && fast.next != null) {            slow = slow.next;            fast = fast.next.next;        }        return slow;    }}

快慢指针还可以解决如下类似的问题，只不过是初始化快慢指针的节点有所不同而已。

1. 输入链表头节点，奇数长度返回中点，偶数长度返回上中点

2. 输入链表头节点，奇数长度返回中点，偶数长度返回下中点

3. 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个

4. 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个

判断链表是否为回文结构

题目链接为：LeetCode 234. Palindrome Linked List

本题比较好理解的一种解法是使用栈的方式，先将节点全部入栈，然后依次弹出并和原链表一一对比。空间复杂度是O(N)。

    // 利用栈O(n)    public static boolean isPalindrome(ListNode head) {        Stack<ListNode> stack = new Stack<>();        ListNode c = head;        while (c != null) {            stack.push(c);            c = c.next;        }        c = head;        while (c != null) {            if (c.val != stack.pop().val) {                return false;            }            c = c.next;        }        return true;    }

本题也可以使用链表操作，将空间复杂度优化为O(1)。

同时本题也需要使用快慢指针找到链表的中间位置，然后中间位置拆分左右两侧的链表来进行比较。整体流程如下图

完整代码见：

class Solution {   // 修改原链表，空间O(1)    public static boolean isPalindrome(ListNode head) {        // 0个节点        // 1个节点 都是回文        if (head == null || head.next == null) {            return true;        }        // 判断两个节点        if (head.next.next == null) {            return head.val == head.next.val;        }        // 判断三个节点        if (head.next.next.next == null) {            return head.val == head.next.next.val;        }        //到这一步，至少有四个节点        // 使用快慢指针        // 奇数来到中点前一个位置(假设为a)和中点后一个位置(假设为b)        // 偶数来到上中点位置(假设为a)和下中点位置(假设为b)        // head ... a 这个链表，链表反转一下 a...head        // 设置两个指针，一个指向a，一个指向b，每个位置对比，结果记录在result中        // 恢复整个链表        ListNode slow = head;        ListNode fast = head.next.next;        while (fast != null && fast.next != null) {            fast = fast.next.next;            slow = slow.next;        }        ListNode a = slow;        ListNode b;        ListNode mid = null;        if (fast != null) {            // 链表个数为奇数            mid = a.next;            b = a.next.next;        } else {            b = a.next;            // 链表个数为偶数        }        // 断开链表        a.next = null;        // 反转前半部分链表        ListNode c = reverse(head);        boolean result = true;        ListNode leftStart = c;        ListNode rightStart = b;        while (leftStart.next != null) {            if (leftStart.val != rightStart.val) {                result = false;            }            leftStart = leftStart.next;            rightStart = rightStart.next;        }        if (leftStart.val != rightStart.val) {            result = false;        }        // leftStart来到开始节点        // rightStart来到末尾节点        ListNode cur = reverse(leftStart);        while (cur.next != null) {            cur = cur.next;        }        if (mid == null) {            cur.next = b;        } else {            cur.next = mid;            mid.next = b;        }        return result;    }    private static ListNode reverse(ListNode head) {        ListNode pre = null;        ListNode cur = head;        while (cur != null) {            ListNode tmp = cur.next;            cur.next = pre;            pre = cur;            cur = tmp;        }        return pre;    }}

合并两个及以上有序链表问题

见：合并两个及以上有序链表问题

本文中所有图例见：processon

更多

算法和数据结构笔记

参考资料

算法和数据结构体系班-左程云