leetcode Reverse Linklist 倒置链表

/**
 * Created by chris on 2014/11/11.
  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 ReverseLinkList {

    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m >= n || m <= 0) return head;//1 ≤ m ≤ n ≤ length of list
        ListNode pHead = head;
        ListNode pHeadPre = head;
        ListNode pNext = head;
        int i = 0;
        while (pHead != null){
            i++;
            pHead = pHead.next;
        }
        if (i < n) return head;//n不能大于链表的数目

        pHead = head;
        for (int j = 1; j < m; j++) {	//找到第m个结点
            if (j == m - 1) pHeadPre = pHead;
            pHead = pHead.next;

        }
        pNext = pHead;

        for (int j = 0; j <= n - m; j++) { //找到第n+1个结点
            pNext = pNext.next;
        }
        pHead = reverseList(pHead, n - m + 1, pNext); //逆转m到n,pNext是n+1这个结点

        if (m == 1) { //表示从第一个结点开始逆转
            return pHead;
        }else {       
            pHeadPre.next = pHead;
            return head;
        }
    }

/*链表p,逆转前k个结点,tail指向第k+1个结点*/
    private ListNode reverseList(ListNode p, int k ,ListNode tail) {
        ListNode head = new ListNode(0);
        head.next = tail;
        ListNode next = p ;

        while (p != null && p != tail){
            next = p.next;
            p.next = head.next;
            head.next = p;
            p = next;
        }
        return head.next;
    }
}
Tagged on: , ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.