- 關(guān)鍵字：反轉(zhuǎn)部分鏈表
- 難度：Medium
- 題目大意：反轉(zhuǎn)部分鏈表肿孵，要求遍歷一次鏈表完成
題目：
Reverse a linked list from position m to n. Do it in one-pass.
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
解題思路：
先建立一個(gè)dummy結(jié)點(diǎn)灶壶，pre結(jié)點(diǎn)灾茁、cur結(jié)點(diǎn)牧抽，首先移動(dòng)cur到需要反轉(zhuǎn)的第一個(gè)節(jié)點(diǎn)构回，相應(yīng)的pre移動(dòng)到cur前一個(gè)結(jié)點(diǎn)夏块，用start記錄開始反轉(zhuǎn)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)疏咐，end記錄反轉(zhuǎn)的第一個(gè)結(jié)點(diǎn)，這么說有點(diǎn)繞脐供，舉個(gè)例子：
1 -> 2 -> 3 -> 4 ->5 ->NULL , m=2, n=4
反轉(zhuǎn)步驟：
- 建立dummy結(jié)點(diǎn)：
dummy -> 1 -> 2 -> 3 -> 4 ->5 -> NULL pre=dummy, start=dummy, cur=head; - 移動(dòng)cur到要反轉(zhuǎn)的節(jié)點(diǎn)：此時(shí)浑塞，pre=1, start=1, cur=2, end=2;
- 第一次反轉(zhuǎn)：dummy -> 1 <- 2 -> 3 -> 4 ->5 -> NULL, start=1, pre=2, cur=3, end=2;
- 第二次反轉(zhuǎn)：dummy -> 1 <- 2 <- 3 -> 4 ->5 -> NULL, start=1, pre=3, cur=4, end=2;
- 第三次反轉(zhuǎn)：dummy -> 1 <- 2 <- 3 <- 4 ->5 -> NULL, start=1, pre=4, cur=5; end=2;
- 改變start 和end 的next結(jié)點(diǎn)：start.next = pre, end.next=cur, dummy -> 1->4->3->2->5->NULL
AC代碼：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if(head==null) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode start = dummy;
ListNode cur = head;
for(int i=0;i<m-1;i++) {
pre = cur;
start = pre;
cur = cur.next;
}
ListNode end = cur;
for(int i=0;i<=n-m;i++) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
start.next = pre;
end.next = cur;
return dummy.next;
}
}
