92. 反轉鏈表 II

題目：中等難度

反轉從位置 m 到 n 的鏈表。請使用一趟掃描完成反轉。

說明:
1 ≤ m ≤ n ≤ 鏈表長度。

示例:

輸入: 1->2->3->4->5->NULL, m = 2, n = 4
輸出: 1->4->3->2->5->NULL

解題思路：
1.基礎首先是普通鏈表反轉，也就是需要一個新鏈表頭指針new_head指向新鏈表的頭部，然后從舊鏈表里找到需要反轉的節(jié)點利用頭插法插入到新鏈表里。
2.著重點是找到需要反轉的節(jié)點------按位查找。
3.需要標記舊鏈表里的四個特殊節(jié)點，反轉完畢后連接成目標鏈表。如下圖

4.把反轉后3里找到的四個節(jié)點重新鏈接即可。

總結:主體框架是按位查找+鏈表反轉+重要位置節(jié)點的標記

需要注意的幾個點：

1.以上四個指針的初始賦值問題，第一個指針不能直接賦值head。因為如果m等于1時，這個指針的值應為Null。重點需要注意第一個指針是NULL的情況。
2.反轉時創(chuàng)建了新的鏈表，利用頭插法把舊鏈表的頭結點插到新鏈表時，要提前用一個next指針標記舊鏈表的下一個節(jié)點，不然舊鏈表的頭結點斷開后就找不到新節(jié)點。

附上代碼：

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/class Solution { public:ListNode* reverseBetween(ListNode* head, int m, int n) {ListNode* pre_head=NULL; //反轉部分的前一個節(jié)點——有可能為空（即m為1的情況）ListNode* new_head=NULL; //反轉后的鏈頭ListNode* list_tail=NULL; //反轉后的鏈尾ListNode* result=head; //返回值ListNode* next; //反轉時用來標記原鏈表的指針int len=n-m+1; // 反轉的節(jié)點的數(shù)量// 尋找需要反轉的第一個節(jié)點while(head&&--m) { pre_head=head; //1.指針跟隨head=head->next; //2.指針下移}list_tail=head; //反轉部分之前的鏈頭就是反轉之后的鏈尾//實現(xiàn)反轉部分 while(head&&(len--)) { next=head->next; //先標記原鏈表的下一個節(jié)點head->next=new_head; //把原鏈表的第一個節(jié)點插入到新鏈表的頭new_head=head; //更新新鏈表的頭結點指針head=next; //更新舊鏈表的頭結點指針}list_tail->next=head;//判斷健壯性 --注意pre_head為null的情況if(pre_head) {pre_head->next=new_head;}else{result=new_head;}return result;} };

總結

以上是生活随笔為你收集整理的LeetCode 中等难度 92. 反转链表 II解题思路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。