LeetCode刷题笔记——反转链表_链表相邻节点反转 lertcode

LeetCode刷题笔记——反转链表

题目

给你单链表的头节点 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
图示如下

要先完成这道题，我们需要先了解什么是链表

链表

线性表的链式存储结构称为链表，包括数据域和指针域，但是在Java中是没有指针的概念的，所以我们需要定义一个链表结构的类
1

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

1
2
3
4
5
6

反转链表使用的方法一般都是头插法
1

头插法

整体思想是：在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。下面的图展示了整个流程。

curr：指向待反转区域的第一个节点 left；
next：永远指向 curr 的下一个节点，循环过程中，curr 变化以后 next 会变化；
pre：永远指向待反转区域的第一个节点 left 的前一个节点，在循环过程中不变。

先将 curr 的下一个节点记录为 next；
执行操作 ①：把 curr 的下一个节点指向 next 的下一个节点；
执行操作 ②：把 next 的下一个节点指向 pre 的下一个节点；
执行操作 ③：把 pre 的下一个节点指向 next。

第 1 步完成以后「拉直」的效果如下：
同理 循环right-left 次后就能完成反转链表

以下是实现代码：

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

这里用到了dummyNode（哑结点），也就是虚节点
链表的第一个node，因为没有前驱节点，所以该node需要特殊处理，会导致额外的代码量。如果创建一个dummy，将其作为第一个node的前驱节点，这样链表中所有的node都可以也能够同样的逻辑来处理了。
根据left-1找到left的前驱
然后根据right-left获得头插次数，每次都执行一次上述的操作，就能完成链表反转

leetCode运行结果如下