Reverse Nodes in k-Group

LeetCode笔记 阅读(364)

编号 : 25      
难度 : <font color="red">Hard</font>

# 题目 :  
>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.
>
>**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`
>
>**Note**:
>
>* Only constant extra memory is allowed.
>* You may not alter the values in the list's nodes, only nodes itself may be changed.

# 解 :  
```Cpp
/**
 * 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) {
        
        if(k <= 1)
        {
            return head;
        }
        
        /* 方便最后返回 */
        ListNode preHead(0);
        preHead.next = head;
        
        for(ListNode* pos = &preHead; pos != nullptr;) // pos是子串的preHead
        {
            ListNode* head = pos->next;
            ListNode* tail = head;
            for(int i = 1; i < k && tail != nullptr; i++)
            {
                tail = tail->next;
            }
            if(tail == nullptr)
            {
                break;
            }
            reverse(pos, tail);
            pos = head;
        }

        return preHead.next;
    }

    /* 逆转链表:
     * preHead -> 1 -> 2 -> 3 -> 4 -> tail -> NEXT
     * preHead -> tail -> 4 -> 3 -> 2 -> 1 -> NEXT
     */
    void reverse(ListNode* preHead, ListNode* tail)
    {
        ListNode* left = preHead->next;
        ListNode* current = left->next;
        left->next = tail->next; // 1 -> NEXT
        
        /* 逆转 */
        while(current != tail)
        {
            ListNode* right = current;
            current = current->next;
            right->next = left;
            left = right;
        }
        
        current->next = left;    // tail -> 4
        preHead->next = current; // preHead -> tail
    }
};
```

# 分析 :  
这道题要求将单向链表中每`k`个节点进行反转,但是不足`k`个节点时不反转,并要求 :  
* 空间复杂度是常数
* 必须反转节点,而不能修改节点的值

上述解法中创建了辅助函数`reverse`,这个函数截取整个链表中的一段,将该段进行反转,并保证反转后与原链表的连接正常 :  
```
preHead -> 1 -> 2 -> 3 -> 4 -> tail -> NEXT
preHead -> tail -> 4 -> 3 -> 2 -> 1 -> NEXT
```
* 要逆转的子链为`1 -> 2 -> 3 -> 4 -> tail`

外层函数在原链表中从头开始搜索长度为`k`的子链表,调用`reverse`函数进行逆转,如果剩余的长度不足`k`,则结束。

Markdown使用 帮助


匿名

富强 民主 文明 和谐 自由 平等 公正 法治 爱国 敬业 诚信 友善

匿名

在山的那边,海的那边,有一群蓝精灵。

匿名

在山的那边,海的那边,有一群蓝精灵。