可視化圖解算法：鏈表指定區間反轉

1. 題目

描述

給你單鏈表的頭指針 head 和兩個整數 left 和 right ，其中 left <= right 。請你反轉從位置 left 到位置 right 的鏈表節點，返回 反轉后的鏈表 。

示例1

輸入：

輸入：head = [1,2,3,4,5], left = 2, right = 4
輸出：[1,4,3,2,5]

示例 2

輸入：head = [5], left = 1, right = 1
輸出：[5]

提示：

鏈表中節點數目為 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

2. 解題思路

第1步：定義一個臨時鏈表頭節點。

第2步：定義（找到）截取區間外的指針變量：pre、post，截取區間指針變量：left、right。

第3步：切斷原連接。

第4步：翻轉局部鏈表。

鏈表的局部反轉，可以參考上一篇講解的《可視化圖解算法：反轉鏈表》。

第5步：接回原來的鏈表。

如果文字描述的不太清楚，你可以參考視頻的詳細講解。

Python編碼：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1370258
Java編碼：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1366714
Golang編碼：數據結構筆試面試算法-Go語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Go語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ep1364391

3. 編碼實現

3.1 Python編碼實現

class ListNode:def __init__(self, x):self.val = x  # 鏈表的數值域self.next = None  # 鏈表的指針域# 從鏈表節點尾部添加節點
def insert_node(node, value):if node is None:print("node is None")return# 創建一個新節點new_node = ListNode(value)cur = node# 找到鏈表的末尾節點while cur.next is not None:cur = cur.next# 末尾節點的next指針域連接新節點cur.next = new_node# 打印鏈表（從鏈表頭結點開始打印鏈表的值）
def print_node(node):cur = node# 遍歷每一個節點while cur is not None:print(cur.val, end="\t")cur = cur.next  # 更改指針變量的指向print()def reverseList(left):if left is None:returnpre = None  # （操作的）前序節點cur = left  # （操作的）當前節點nxt = left  # （操作的）下一個節點while cur is not None:nxt = cur.nextcur.next = prepre = curcur = nxt#
# 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可
#
#
# @param head ListNode類
# @param m int整型
# @param n int整型
# @return ListNode類
#
class Solution:def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:# write code here# 1. 定義一個臨時鏈表頭節點tmp_head = ListNode(-1)tmp_head.next = head# 2.定義（找到）截取區間外的指針變量：pre、post，截取區間指針變量：left、rightpre = tmp_headfor i in range(m - 1):pre = pre.nextleft = pre.nextright = tmp_headfor i in range(n):right = right.nextpost = right.next# 3.切斷鏈接pre.next = Noneright.next = None# 4. 翻轉局部鏈表reverseList(left)# 5.接回原來的鏈表pre.next = rightleft.next = postreturn tmp_head.nextif __name__ == '__main__':root = ListNode(1)insert_node(root, 2)insert_node(root, 3)insert_node(root, 4)insert_node(root, 5)print_node(root)s = Solution()head = s.reverseBetween(root, 2, 4)print_node(head)

3.2 Java編碼實現

package LL02;import javax.swing.plaf.nimbus.NimbusLookAndFeel;public class Main {//定義鏈表節點static class ListNode {private int val;  //鏈表的數值域private ListNode next; //鏈表的指針域public ListNode(int data) {this.val = data;this.next = null;}}//添加鏈表節點private static void insertNode(ListNode node, int data) {if (node == null) {return;}//創建一個新節點ListNode newNode = new ListNode(data);ListNode cur = node;//找到鏈表的末尾節點while (cur.next != null) {cur = cur.next;}//末尾節點的next指針域連接新節點cur.next = newNode;}//打印鏈表（從頭節點開始打印鏈表的每一個節點）private static void printNode(ListNode node) {ListNode cur = node;//遍歷每一個節點while (cur != null) {System.out.print(cur.val + "\t");cur = cur.next; //更改指針變量的指向}System.out.println();}public static class Solution {/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可** @param head ListNode類* @param m    int整型* @param n    int整型* @return ListNode類*/public ListNode reverseBetween(ListNode head, int m, int n) {// write code here//1. 定義一個臨時鏈表頭節點ListNode tmpHead = new ListNode(-1);tmpHead.next = head;//2.定義（找到）截取區間外的指針變量：pre、post，截取區間指針變量：left、rightListNode pre = tmpHead;for (int i = 0; i < m - 1; i++) {pre = pre.next;}ListNode left = pre.next;ListNode right = tmpHead;for (int i = 0; i < n; i++) {right = right.next;}ListNode post = right.next;//3.切斷鏈接pre.next = null;right.next = null;//4.反轉局部鏈表reverseList(left);//5.接回原來的鏈表pre.next = right;left.next = post;return tmpHead.next;}private void reverseList(ListNode left) {ListNode pre = null; //前序節點ListNode cur = left; //（操作的）當前節點ListNode nxt = left;//（操作的）下一個節點while (cur != null) {nxt = cur.next;cur.next = pre;pre = cur;cur = nxt;}}}public static void main(String[] args) {ListNode root = new ListNode(1);insertNode(root, 2);insertNode(root, 3);insertNode(root, 4);insertNode(root, 5);printNode(root);Solution solution = new Solution();ListNode head = solution.reverseBetween(root, 2, 4);printNode(head);}
}

3.3 Golang編碼實現

package mainimport ("fmt"
)type ListNode struct {Val  int       //鏈表的數值域Next *ListNode //鏈表的指針域
}/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可*** @param head ListNode類* @param m int整型* @param n int整型* @return ListNode類*/
func reverseBetween(head *ListNode, m int, n int) *ListNode {// write code here//1. 定義一個臨時鏈表頭節點tempHead := &ListNode{Val: -1}tempHead.Next = head//2.定義（找到）截取區間外的指針變量：pre、post，截取區間指針變量：left、rightpre := tempHeadfor i := 0; i < m-1; i++ {pre = pre.Next}left := pre.Nextright := tempHeadfor i := 0; i < n; i++ {right = right.Next}post := right.Next//3.切斷鏈接pre.Next = nilright.Next = nil//4.翻轉局部鏈表reverseList(left)//5.接回原來的鏈表pre.Next = rightleft.Next = postreturn tempHead.Next
}func reverseList(left *ListNode) {var pre *ListNode //（操作的）前序節點cur := left       //（操作的）當前節點nxt := left       //（操作的）下一個節點for cur != nil {nxt = cur.Nextcur.Next = prepre = curcur = nxt}
}
func main() {root := &ListNode{Val: 1}root.Insert(2)root.Insert(3)root.Insert(4)root.Insert(5)root.Print()node := reverseBetween(root, 2, 4)node.Print()
}// Insert 從鏈表節點尾部添加節點
func (ln *ListNode) Insert(val int) {if ln == nil {return}//創建一個新節點newNode := &ListNode{Val: val}cur := ln//找到鏈表的末尾節點for cur.Next != nil {cur = cur.Next}//末尾節點的next指針域連接新節點cur.Next = newNode
}// Print 從鏈表頭結點開始打印鏈表的值
func (ln *ListNode) Print() {if ln == nil {return}cur := ln//遍歷每一個節點for cur != nil {fmt.Print(cur.Val, "\t")cur = cur.Next //更改指針變量的指向}fmt.Println()
}

如果上面的代碼理解的不是很清楚，你可以參考視頻的詳細講解。

Python編碼：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1370258
Java編碼：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1366714
Golang編碼：數據結構筆試面試算法-Go語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Go語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ep1364391

4.小結

對于鏈表內指定區間反轉的反轉，可以通過5步操作完成：

（1）定義一個臨時鏈表頭節點；（2）定義（找到）截取區間外的指針變量：pre、post，截取區間指針變量：left、right；（3）切斷鏈接；（4）翻轉局部鏈表；（5）接回原來的鏈表。對于第4步局部反轉用到了上一篇所講的內容。

更多算法視頻講解，你可以從以下地址找到：

Python編碼實現：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1509965
Java編碼實現：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1510007
Golang編碼實現：數據結構筆試面試算法-Go語言版_嗶哩嗶哩_bilibili數據結構筆試面試算法-Go語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ep1509945