首页 > 代码库 > leetcode--Reverse Linked List II

leetcode--Reverse Linked List II

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->NULLm = 2 and n = 4,

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

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

public class Solution {    /**	 * The algorithm is straightforward. We first move one pointer to the m-th node of	 * the list and then reverse the links of the following n - m nodes;	 * @param head  --ListNode, the head node of a linked list	 * @param m --int, the start nodes	 * @param n --int, the ending nodes	 * @return  ListNode --head of the new linked list	 * @author Averill Zheng	 * @version 2014-06-12	 * @since JDK 1.7	 */    public ListNode reverseBetween(ListNode head, int m, int n) {        ListNode newHead = new ListNode(0);		newHead.next = head;		ListNode previous = null;;		ListNode firstNode = newHead;		int i = 0;		while(i < m){			previous = firstNode;			firstNode = firstNode.next;			++i;		}				//remember previous.next = firstNode;		ListNode current = firstNode.next;		ListNode tail = null;		int j = 0;		while(j < n - m){			tail = firstNode;			firstNode = current;			current = current.next;			firstNode.next = tail;			++j;		}			previous.next.next = current;		previous.next = firstNode;		newHead = newHead.next;		return newHead;    }}