「链表」专题 1:在链表中穿针引线


「链表」专题 1:在链表中穿针引线

准备算法面试一定不能忽略基础,算法面试中链表的问题是经常出现的。

链表是一种特殊的线性结构,由于不能像数组一样进行随机的访问,所以和链表相关的问题有它自身的特点。其中一点就是「穿针引线」。

例1:「力扣」第 206 题:反转链表

传送门:反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

分析:分析这道问题的时候写的草稿。

LeetCode 第 206 题:反转链表

题目的要求是节点是不动的,而应该改变的是节点的 next 指针的方向。而不应该是去修改链表的值,使得这个新的链表看起来是反向的。指针变化的过程其实并不复杂,关键是我们把图画出来,需要多少个临时变量,指针变化过程也就一目了然了。我们可以看到,reverseList 的参数是一个 ListNode 类型的对象,即对象的头结点。

Java 代码:

class ListNode {

    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

public class Solution {

    /**
     * 1、结合自己画的图并不难写出逻辑,把图画出来,迭代的思路就已经有了
     * 2、借助三个指针:pre、current、next 完成链表的反转
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        // 初始化上一个指针
        ListNode pre = null;
        // 初始化当前指针
        ListNode current = head;
        while (current != null) {
            // 第 1 步:先把 next 存起来,下一轮迭代要用到
            ListNode next = current.next;
            // 第 2 步:实现当前节点的 next 指针的反转
            current.next = pre;

            // 第 3 步:重新定义下一轮迭代的循环变量
            pre = current;
            current = next;
        }
        // 遍历完成以后,原来的最后一个节点就成为了 pre
        // 这个 pre 就是反转以后的新的链表的头指针
        return pre;
    }
}

看看代码是不是很简单。这个解法的时间复杂度是 $O(n)$,因为它仅仅遍历了一次链表,空间复杂度是$O(1)$,因为这里仅仅使用了有限个的“指针”,帮助我们完成了链表的反转操作。

补充:如果不使用“穿针引线”,还可以用递归完成。

练习1:「力扣」第 92 题:反转从位置 m 到 n 的链表,k 个组进行一次反转

传送门:英文网址:92. Reverse Linked List II ,中文网址:92. 反转链表 II

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

LeetCode 第 92 题:反转从位置 m 到 n 的链表,k 个组进行一次反转-1

Java 代码:

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        // 创建一个虚拟的结点(dummy)
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode pre = dummy;
        int k = 0;

        while (++k < m) {
            if (pre != null) {
                pre = pre.next;
            }
        }

        // tail 是尾巴的意思
        ListNode tail = pre.next;
        while (++k <= n) {
            ListNode temp = pre.next;

            pre.next = tail.next;
            tail.next = tail.next.next;
            pre.next.next = temp;
        }
        return dummy.next;
    } 
}

Java 代码:

public class Solution2 {

    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        for (int i = 0; i < m - 1; i++) {
            // pre 指针向后移动
            pre = pre.next;
        }
        // System.out.println(pre.val);

        ListNode p = pre.next;
        ListNode curNode;
        for (int i = 0; i < n - m; i++) {
            curNode = p.next;
            p.next = curNode.next;
            curNode.next = pre.next;
            pre.next = curNode;
        }
        return dummy.next;
    }
}

Java 代码:

public ListNode reverseBetween(ListNode head, int m, int n) {
    // 设置 dummyNode 是这一类问题的一般做法
    ListNode dummyNode = new ListNode(-1);
    dummyNode.next = head;
    ListNode pre = dummyNode;
    for (int i = 0; i < m - 1; i++) {
        pre = pre.next;
    }
    ListNode cur = pre.next;
    ListNode next;
    for (int i = 0; i < n - m; i++) {
        next = cur.next;
        cur.next = next.next;
        next.next = pre.next;
        pre.next = next;
    }
    return dummyNode.next;
}

另一种解法:来自“小吴”的动图,比较自然,但是代码写起来不够简洁。

图示:

LeetCode 第 92 题:反转从位置 m 到 n 的链表,k 个组进行一次反转-2

Python 代码:
LeetCode 第 92 题:反转从位置 m 到 n 的链表,k 个组进行一次反转-3

(本节完)


文章作者: liweiwei1419
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 liweiwei1419 !
评论
 上一篇
「链表」专题 2:测试的链表程序 「链表」专题 2:测试的链表程序
「链表」专题 2:测试的链表程序为了测试我们写的代码是否正确,我们需要自己写两个个方法,这两个方法对于调试代码来说是十分有帮助的。 编写辅助函数:通过一个数组创建一个链表Java 代码: public ListNode createLink
下一篇 
「力扣」第 345 题:反转字符串中的元音字母(简单) 「力扣」第 345 题:反转字符串中的元音字母(简单)
「力扣」第 345 题:反转字符串中的元音字母(简单) 中文网址:345. 反转字符串中的元音字母; 英文网址:345. Reverse Vowels of a String 。 编写一个函数,以字符串作为输入,反转该字符串中的元音字母
  目录