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

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

作者:Grey

原文地址:

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

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

反转单链表

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

思路如下

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

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

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

以下是示例图

假设原始链表如下

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

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

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

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

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

最后返回 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;
        }

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

接下来是普遍情况:

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

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

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

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

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

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

其中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 

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

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

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

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

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

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

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

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

        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 

完整代码见:

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 -> e
k = 3

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

如果是下述情况

...-> start -> b -> c -> null
k = 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 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)

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

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

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

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

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

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

完整代码见:

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

更多

算法和数据结构笔记

参考资料

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

文章来源于互联网:基础数据结构之链表相关的一些问题

THE END
分享
二维码