Label the m-th node(label) and the node before m-th node (prelabel). Insert nodes afterwards till the n-th node one by one between prelabel and label.Reverse a linked list from position m to n. Do it in-place and in one-pass.For example: Given1->2->3->4->5->NULL
, m = 2 and n = 4,return1->4->3->2->5->NULL
.Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.
prelabel: 1
label: 2
1 -> 3 -> 2 -> 4 -> 5
1 -> 4 -> 3 -> 2 -> 5
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) { if (head == null) return null; if (m == n) return head; ListNode dummy = new ListNode(0); dummy.next = head; int index = 1; ListNode prelabel = dummy; for (index = 1; index < m; index++) { prelabel = head; head = head.next; if (head == null) return null; } ListNode prev = head; ListNode label = head; head = head.next; //index ++; for (index = m + 1; index <= n; index++) { label.next = head.next; prelabel.next = head; head.next = prev; prev = head; head = label.next; } return dummy.next; } }
No comments:
Post a Comment