离线下载
PDF版 ePub版

柯于旺 · 更新于 2018-11-28 11:00:43

Reverse Nodes in k-Group(在K组链表中反转结点)

原文

给定一个链表,在一定时间内反转这个链表的结点,并返回修改后的链表。

如果结点数不是K的倍数,那么剩余的结点就保持原样。

你不应该在结点上修改它的值,只有结点自身可以修改。

只允许使用常量空间。

例如

给定链表: 1->2->3->4->5

对于 k = 2,你应该返回: 2->1->4->3->5

对于 k = 3,你应该返回: 3->2->1->4->5

翻译

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.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        auto node = head;
        for(int i = 0; i < k; ++ i) {
            if(!node) return head;
            node = node->next;
        }

        auto new_head = reverse(head, node);
        head->next = reverseKGroup(node, k);
        return new_head;        
    }

    ListNode* reverse(ListNode* start, ListNode* end) {
        ListNode* head = end;

        while(start != end) {
            auto temp = start->next;
            start->next = head;
            head = start;
            start = temp;
        }

        return head;
    }
};