转变命运！揭秘反转链表的神奇算法！

我不是女神ヾ 2024-02-20 09:48 27阅读 0赞

#### 目录 ####

*   *  使用虚拟头节点来辅助实现链表反转
     *  直接操作链表实现反转
     *  使用递归来实现链表反转
     *  指定区间反转
     *   *  头插法
         *  穿针引线法

链表是计算机科学中常用的数据结构之一，它由一系列节点构成，每个节点包含一个值和指向下一个节点的指针。链表的灵活性使其在许多场景下被广泛应用，但其中的一个常见问题是如何反转链表。我们来了解下面两种实现链表反转的方法。

### 使用虚拟头节点来辅助实现链表反转 ###

首先我们先来建立一个虚拟节点dummyNode，并且使dummyNode.next=head,这样就可以很好的简化我们的操作。

public ListNode reverseList(ListNode head) {
        
            ListNode dummyNode = new ListNode(-1);
            ListNode cur = head;
            while (cur != null) {
        
                ListNode next = cur.next;
                cur.next = dummyNode.next;
                dummyNode.next = cur;
                cur = next;
            }
            return dummyNode.next;
        }

在循环体中，首先将cur.next赋值给next,用于保存cur的下一个节点。然后将dummyNode.next赋值给cur.next,即将cur与dummyNode相连，形成一个新的链表。接着将cur赋值给dummyNode.next,即将dummyNode与下一个节点相连。最后将next赋值给cur,继续遍历链表。

### 直接操作链表实现反转 ###

![在这里插入图片描述][b46a17f14f6840ad85cc6cc5f40a56a2.png]

public ListNode reverseList(ListNode head) {
        
            ListNode pre = null;
            ListNode cur = head;
            while (cur != null) {
        
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            return pre;
        }

方法内部定义了两个变量pre和cur,分别表示当前节点的前一个节点和当前节点。初始时，pre为null,cur为head。  
接下来是一个while循环，当cur不为null时，循环继续执行。在循环内部，首先将cur的下一个节点赋值给next,然后将cur的next指针指向pre,即将当前节点cur与前一个节点pre相连。接着将pre赋值给cur,表示当前节点变为前一个节点。最后将next赋值给cur,表示将当前节点更新为下一个节点。  
循环结束后，pre即为反转后的链表头节点，返回pre即可。

### 使用递归来实现链表反转 ###

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

1.  首先判断链表是否为空或只有一个节点，如果是，则直接返回head,因为不需要反转。
2.  如果链表有多个节点，递归调用reverseList(head.next),将链表的剩余部分反转，并将新的头节点赋值给newHead。
3.  接下来，将原链表的尾节点与新链表的头部相连，即将head.next.next指向head。
4.  将原链表的尾节点置为null,表示已经处理完毕。
5.  最后返回新的头节点newHead。

### 指定区间反转 ###

指定区间反转我们有两种方法：头插法与穿针引线法。  
我们以[力扣92题][92]做测试

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

#### 头插法 ####

具体思路就是在需要反转的区间内，每遍历一个节点，就让这个新节点来到反转的起始位置  
![在这里插入图片描述][d0356eb35dfb4b07a3389f68f426707b.png]

public ListNode reverseBetween(ListNode head, int left, int right) {
        
            if (head == null) {
        
                return head;
            }
            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 = null;
            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;
        }

*  首先，如果链表为空(即head为null),则直接返回空链表。
 *  接下来，创建一个虚拟节点dummyNode,并将其next指针指向head。这样做的目的是为了方便处理边界情况，例如当left为1时，不需要对原始链表进行任何操作，直接返回dummyNode即可。
 *  然后，使用一个for循环遍历链表，找到第left个节点的前一个节点pre。接着，将cur指针指向pre的下一个节点，即第left个节点。
 *  接下来，使用另一个for循环遍历链表，从第left个节点开始，直到第right个节点。在每次循环中，首先将next指针指向cur的下一个节点，然后将cur的next指针指向next的下一个节点，将next的next指针指向pre的下一个节点，最后将pre的next指针指向next。这样就完成了链表中从第left个节点到第right个节点之间的节点反转操作。
 *  最后，返回dummyNode的next指针，即反转后的链表的头节点。

#### 穿针引线法 ####

大体思路就是确定好需要反转的部分，用一个反正链表的方法把需要反转的部分反转然后接回去。  
![在这里插入图片描述][c7cd809f2fa64e83873ca4ef0a8c3390.png]

public ListNode reverseBetween(ListNode head, int left, int right) {
        
            ListNode dummyNode = new ListNode(-1);
            dummyNode.next = head;
            ListNode pre = dummyNode;
            for (int i = 0; i < left - 1; i++) {
        
                pre = pre.next;
            }
            ListNode rightNode = pre;
            for (int i = 0; i < right - left + 1; i++) {
        
                rightNode = rightNode.next;
            }
            ListNode leftNode = pre.next;
            ListNode succ = rightNode.next;
            rightNode.next = null;
            reverse(leftNode);
            pre.next = rightNode;
            leftNode.next = succ;
            return dummyNode.next;
        }
    
        public void reverse(ListNode head) {
        
    
            ListNode prev = null;
            ListNode cur = head;
            while (cur != null) {
        
                ListNode next = cur.next;
                cur.next = prev;
                prev = cur;
                cur = next;
            }

1.  创建一个虚拟头节点dummyNode,并将其next指向head。
2.  创建一个指针pre,初始化为dummyNode。
3.  遍历链表，找到第left-1个节点的前一个节点，将其赋值给pre。
4.  找到第left个节点的前一个节点，将其赋值给rightNode。
5.  找到第right个节点的下一个节点，将其赋值给leftNode。
6.  找到第right+1个节点，将其赋值给succ。
7.  将rightNode的next指针设为null,表示反转后的链表不包含第right个节点。
8.  调用reverse方法，反转leftNode到rightNode之间的所有节点。
9.  将pre的next指针指向rightNode,表示反转后的链表包含第left个节点和第right个节点。
10. 将leftNode的next指针指向succ,表示反转后的链表包含第left+1个节点和第right+1个节点。
11. 返回dummyNode的next指针，即反转后的链表的头节点。

[b46a17f14f6840ad85cc6cc5f40a56a2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/c89c8e194bbf4103802d22bc7384d509.png
[92]: https://leetcode.cn/problems/reverse-linked-list-ii/description/
[d0356eb35dfb4b07a3389f68f426707b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/cb7990b8507f4a8db4a73acadf7f5f41.png
[c7cd809f2fa64e83873ca4ef0a8c3390.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/9280273c044149da8987a3bfbc57c951.png