92. Reverse Linked List II

Reverse a linked list from position m to n. Do it in one-pass.
將位置m的鏈接列表反轉到n。 一次通過。

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

代碼

/*** 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) {int change_len=n-m+1; //計算需要逆置的節點個數ListNode *pre_head=NULL; //初始化開始逆置的節點的前驅ListNode *result=head; //最終轉換后的鏈表頭節點，非特殊情況即為headwhile(head && --m){pre_head=head; //記錄head的前驅head=head->next;}ListNode *modify_list_tail = head; //將modify_list_tail指向當前的head，即逆置后的鏈表尾ListNode *new_head = NULL;while(head&&change_len){//逆置change_len個節點ListNode *next=head->next;head->next=new_head;new_head=head;head=next;change_len--; //每完成一個節點逆置，change_len--；}modify_list_tail->next=head; //連接逆置后的鏈表尾與逆置段的后一個節點if(pre_head){//如果pre_head不空，說明不是從第一個節點開始逆置的，m>1pre_head->next=new_head; //將逆置鏈表開始的節點前驅與逆置后的頭節點連接}else{//如果pre_head為空，說明m==1，從第一個節點開始逆置，結果即為逆置后的頭節點result=new_head;}return result;} };

分析

首先找到四個關鍵的節點：逆置段頭節點的前驅、逆置前頭節點即逆置后尾節點、逆置前尾節點即逆置后頭節點、逆置段尾節點的后繼；

總結

以上是生活随笔為你收集整理的LeetCode 92. Reverse Linked List II的全部內容，希望文章能夠幫你解決所遇到的問題。

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