質問する

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.k is a positive integer and is less than or equal to the length of the linked 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 list's nodes, only nodes themselves may be changed.

せいげんじょうけん

The number of nodes in the list is in the range sz.

1 ≤\leq≤ sz ≤\leq≤ 5000

0 ≤\leq≤ Node.val ≤\leq≤ 1000

1 ≤\leq≤ k ≤\leq≤ sz

Follow-up: Can you solve the problem in O(1) extra memory space?

に近づく

リンクリストと整数kを返すとkセットのリンクリストに反転する問題.
キーは、リンクリストのポインタをどのように管理するかです.
私なら.

現在保存するリンクリストは、前のノード、後のノード(前の最初のノードを置換)および後のノードに対する最初のリンクリスト

である.

このギフトバッグ「逆転」

より前のノードnextに逆結果リンクリスト

が保存する.

が逆転すると、最後のノードnextで次のグループの最初のリンクドロップダウン

が初期化される.
この方式が展開された

結果は安定した.

答案用紙

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
   
    public ListNode reverseKGroup(ListNode head, int k) {
        if(null == head || null == head.next || k == 1)
            return head;

        ListNode lastNode = head;
        ListNode nextPeriodNode = getNode(head, k + 1);
        ListNode ret = getReversedNode(head, k);

        lastNode.next = nextPeriodNode;

        ListNode curNode = nextPeriodNode;
        while(null != curNode){
            ListNode prevNode = lastNode;
            lastNode = curNode;
            nextPeriodNode = getNode(curNode, k + 1);

            ListNode reversedNode = getReversedNode(curNode, k);
            if(null == reversedNode)
                break;

            prevNode.next = reversedNode;
            lastNode.next = nextPeriodNode;

            curNode = nextPeriodNode;
        }


        return ret;
    }

    /**
     *
     * @param head
     * @return reverse 이후 첫번째 노드
     */
    ListNode getReversedNode(ListNode head, int k){
        if(null == head)
            return null;

        if(1 == k)
            return head;

        ListNode curNode = head;
        for(int i = 1; i <= k; ++i){
            if(null == curNode)
                return null;
            curNode = curNode.next;
        }

        ListNode prevNode = null;
        curNode = head;
        ListNode nextNode = null;
        for(int i = 1; i <= k ; ++i){
            nextNode = curNode.next;
            curNode.next = prevNode;
            prevNode = curNode;
            curNode = nextNode;
        }
        head.next = null;
        return prevNode;
    }

    ListNode getNode(ListNode head, int k){
        if(null == head)
            return null;

        ListNode node = head;
        for(int i = 1; i < k; ++i){
            if(null == node)
                return null;
            node = node.next;
        }

        return node;
    }
}