25. Reverse Nodes in k-Group

25. Reverse Nodes in k-Group


25. Reverse Nodes in k-Group

Description

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 nodes, only nodes itself may be changed.

Only constant memory is allowed.

Example

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

Translation

给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表。

k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么将最后剩余节点保持原有顺序。

Notes:

  • 你的算法只能使用常数的额外空间。
  • 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

Ideas

使用栈,当栈内的元素足够k个,弹出所有元素形成新的链表。不足k个元素时入栈。

Note

注意测试数据:
[],1

Accept Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class ReverseNodes {
    public ListNode reverseKGroup(ListNode head, int k) {
        Stack<ListNode> stack = new Stack<>();
        int index = 0;
        ListNode result = null;
        ListNode left = null;
        ListNode right;
        boolean isFirst = true;
        while (head != null) {
            right = head;
            head = head.next;
            right.next = null;
            stack.push(right);
            index++;
            if (k == index) {
                index = 0;
                if (isFirst) {
                    result = revers(stack);
                    left = result;
                    isFirst = false;
                } else {
                    left.next = revers(stack);
                }
                while (left.next != null) {
                    left = left.next;
                }
            }
        }
        while (!stack.empty()) {
            if (left == null) {
                result = stack.remove(0);
                left = result;
            } else {
                left.next = stack.remove(0);
                left = left.next;
            }
        }
        return result;
    }

    private ListNode revers(Stack<ListNode> stack) {
        ListNode head;
        ListNode temp = stack.pop();
        head = temp;
        while (!stack.empty()) {
            temp.next = stack.pop();
            temp = temp.next;
        }
        return head;
    }
}

转载请注明出处
本文链接:http://zdran.com/20180330.html