Reverse Linked List II (Java)

LeetCode

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,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

	/*
	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,
	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) {
	if (head==null || head.next==null){
	return head;
	}
	ListNode preHead=new ListNode(0);
	preHead.next=head;
	ListNode pre=preHead;
	ListNode current=head;
	ListNode end=head;
	int countM=1;
	int countN=1;
	// find M point and N point
	while (countM<m || countN<n ){
	if (countM<m){
	pre=pre.next;
	current=current.next;
	countM++;
	}
	if (countN<n){
	end=end.next;
	countN++;
	}
	}
	// reverse from M point to N Point
	reverse(pre, end.next);
	return preHead.next;
	}
	private void reverse(ListNode pre, ListNode endNext){
	ListNode cur=pre.next;
	while (cur.next!=endNext){
	ListNode next=cur.next;
	ListNode temp=pre.next;
	pre.next=next;
	cur.next=next.next;
	next.next=temp;
	}
	}
	}

view raw ReverseLinkedListII.java hosted with ❤ by GitHub