LeetCode [92] Reverse Linked List II

 92. Reverse Linked List II

Medium

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *reverseBetween(ListNode *head, int m, int n) { ListNode *H = new ListNode(0); H->next = head; ListNode *ps; ListNode *start = H; for(int i=0; i<m && start; ++i){ ps = start; start = start->next; } if(start){ for(int i=0; i<n-m && start->next; ++i){ ListNode *p = start->next; ListNode *next = p->next; start->next = next; p->next = ps->next; ps->next = p; } } return H->next; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseBetween(ListNode head, int m, int n) { int l = 0; ListNode H = new ListNode(); H.next = head; ListNode p = H; ListNode left = null, right = null; while(p!=null){ ListNode next = p.next; if(l==m-1){ left = p; right = p.next; }else if(l>m && l<=n){ p.next = left.next; left.next = p; if(l==n){ right.next = next; break; } } p = next; l++; } return H.next; } }