leetcode Reverse Nodes in k-group 链表按组排序

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5

----------------------------------------
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class ReverseNodesInKGroup {
    public ListNode reverseKGroup(ListNode head, int k) {

        ListNode pHead =null;//指向已经排好序的list的第一个结点,最后返回
        ListNode pTail = null;//指向已经排好序的list的最后一个结点
        ListNode p = head;//用p遍历
        ListNode pNext  =head;//pNext指向每组排序的下一组的第一个结点

        while (p != null ) {

                for (int i = 0; i <k-1 && pNext != null; i++) {
                    pNext = pNext.next;
                }
                if (pNext != null)
                    pNext = pNext.next;//指向下一组需逆置的链表的第一个结点

                p = reverseList(p, k, pNext);//逆转list
                if (pTail != null) { //不是第一次,就把返回的p尾插到pHead
                    pTail.next = p;


                }else {
                    pTail = p;//第一次,就指向第一个排好序的list
                    pHead  = p;
                }

                while (pTail.next != null){ //移到最后
                    pTail = pTail.next;
                }
                p = pNext; //从新组开始
            }//end of while

        return pHead;
    }//end of reverseKgroup


    private ListNode reverseList(ListNode p, int k ,ListNode tail) {

        ListNode ptr = p;
        int count = 0;
        while (ptr != null) {
            count++;
            ptr = ptr.next;
        }
        if (count < k)//不够长度进行逆转
            return p;

        ListNode head = new ListNode(0);
        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.