首页 > 代码库 > [leetcode]Reverse Linked List II

[leetcode]Reverse Linked List II

问题描述:

Reverse a linked list from position m ton. 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 ≤ mn ≤ length of list.


基本思路:

思路很简单,翻转链表注意指针的指向即可。

代码:

public ListNode reverse(ListNode head,int n)  //Java
	  {
		ListNode   tmp = head;
		int step = 1;
		tmp = tmp.next;
		ListNode tmphead = head;
		ListNode p = null;
		ListNode pre = head;
		while(step < n){
			 p = tmp.next;
			tmp.next = head;
			head = tmp;
			pre.next = p;
//			head.next = null;
			tmp = p;
			step++;
		}
		tmphead.next = p;
		return head;
	  }
	public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null || head.next == null || m==n)
        	return head;
        ListNode result = new ListNode(0);
        result.next = head;
        ListNode p = head;
        ListNode pre =result;
        int pos = 1;
        while(pos != m){
        	pre = p;
        	p = p.next;
        	pos++;
        	
        }
        ListNode tmphead = reverse(p, n-m+1);
        pre.next = tmphead;
        return result.next;
    }


[leetcode]Reverse Linked List II