Q: 有一個鏈表ListNode head, 反轉其中的第m節(jié)到第n節(jié)缰揪。
比如 1->2->3->4->5, 反轉2到4節(jié)。結果是 1->4->3->2->5.
思路
-
先確定幾個位置葱淳，如圖：
圖片發(fā)自簡書App 將begin 到 end 的這一段進行反轉钝腺。
用before begin 去連反轉后那段的頭，用反轉后那段的尾巴去連after end.
需要注意的地方：
邊界上的反轉可能會使鏈表斷開（我寫的時候卡在這點上一段時間）赞厕。
public class ListNode {
public int val;
public ListNode next;
public ListNode (int val) {
this.val = val;
}
}
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null) { return null; }
ListNode beforeBegin;
ListNode afterEnd;
ListNode end;
ListNode begin;
ListNode dummy = new ListNode(-1);
dummy.next = head;
beforeBegin = dummy;
for (int i = 0; i < m - 1; i++) {
beforeBegin = beforeBegin.next;
}
begin = beforeBegin.next;
end = beforeBegin.next;
for (int i = 0; i < n - m; i++) {
end = end.next;
}
afterEnd = end.next;
beforeBegin.next = null;
end.next = null;
ListNode middle = simpleReverse(begin);
beforeBegin.next = middle;
ListNode middleTail = middle;
while(middleTail.next !=null) {
middleTail = middleTail.next;
}
middleTail.next = afterEnd;
return dummy.next;
}
private ListNode simpleReverse(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy;
ListNode cur = head;
while (cur != null) {
ListNode ne = cur.next;
cur.next = prev;
prev = cur;
cur = ne;
}
dummy.next.next = null;
return prev;
}
// create a Linked List for testing
public ListNode createList(int n) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
for (int i=1; i<=n; i++) {
cur.next = new ListNode(i);
cur = cur.next;
}
return dummy.next;
}
// Test methdod
public static void main(String[] args) {
Test test = new Test();
ListNode head = test.createList(8);
ListNode testList = test.reverseBetween(head, 1, 2);
ListNode cur = testList;
while(cur!=null) {
System.out.print(cur.val + " ");
cur = cur.next;
}
}
// Test results
// reverseBetween(head, 1, 2) -> 2 1 3 4 5 6 7 8
// reverseBetween(head, 1, 8) -> 8 7 6 5 4 3 2 1
// reverseBetween(head, 1, 1) -> 1 2 3 4 5 6 7 8
// reverseBetween(head, 8, 8) -> 1 2 3 4 5 6 7 8
// reverseBetween(head, 2, 7) -> 1 7 6 5 4 3 2 8
// reverseBetween(head, 2, 8) -> 1 8 7 6 5 4 3 2