92.|92. Reverse Linked List II 92.ReverseLinkedListII

Description Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
【92.|92. Reverse Linked List II】return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
Solution Iterative
思路如下：

首先找到开始reverse的节点的前一个节点before
reverse从before + 1到before + n - m + 1这个区间的节点
把链表拼起来

是一道考察细节的题，很容易把指针搞乱掉啊，必须二刷。

/** * 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 (m < 1 || n < 1 || m >= n) { return head; }ListNode dummy = new ListNode(0); dummy.next = head; ListNode before = dummy; for (int i = 0; i < m - 1; ++i) { before = before.next; }// revert [indexOf(before) + 1, indexOf(before) + n - m + 1] ListNode prev = before; ListNode curr = prev.next; for (int i = 0; i < n - m + 1; ++i) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } before.next.next = curr; before.next = prev; return dummy.next; } }

Insert node, time O(n), space O(1)
二刷发现没多难啊，换一种思路，将m到n之间的每个节点移到m-1后面即可。

/** * 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 (m == n) { return head; }ListNode dummy = new ListNode(0); dummy.next = head; ListNode tail = dummy; for (int i = 1; i < m; ++i) { tail = tail.next; }ListNode prev = tail.next; for (int i = 0; i < n - m; ++i) { // move prev.next to the between of tail and tail.next ListNode curr = prev.next; prev.next = curr.next; curr.next = tail.next; tail.next = curr; }return dummy.next; } }