For example:
Given
1->2->3->4->5->NULL
, m = 2 and n = 4,
return
1->4->3->2->5->NULL
.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { // O(helper, pre)->O(2)->O(1, last)->O(3, cur)->O(4) if (m == n) return head; ListNode helper = new ListNode(0); helper.next = head; ListNode pre = helper; // pre is the node that before mth node for (int i = 1; i < m; i++) pre = pre.next; // last is movable, but it always points to the same node (only last.next is changed) ListNode last = pre.next; // cur is the node after last ListNode cur = last.next; int count = 0; // Number of move while (count < n-m) { last.next = cur.next; cur.next = pre.next; pre.next = cur; cur = last.next; count++; } return helper.next; } }
No comments:
Post a Comment