Reverse Linked List II
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given
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.
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) { // Start typing your Java solution below // DO NOT write main() function if(head==null || head.next == null) return head; ListNode prev = new ListNode(0); prev.next=head; head=prev; ListNode n1=head; int k=m-1; while(k>0){ n1=n1.next; k--; } prev=n1; n1=n1.next; k=n-m; while(n1.next!=null && k>0){ ListNode temp =n1.next; n1.next=temp.next; temp.next=prev.next; prev.next=temp; k--; } return head.next; } }
3 comments:
Fantastic post - thanks so much. here's another good reference with some alternative solutions to reversing a linked list:
how to reverse a linked list
Thanks for viewing and sharing the post!
why you need to put a dummy node in ahead of head? I know the dummy node is for considering edge cases like the first node in the linkedlist. But I am still confused if we really need it.
Post a Comment