欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[LeetCode] 25、K 个一组翻转链表

程序员文章站 2022-03-18 09:33:19
...

题目描述

给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。(要求空间O(1)O(1)

给定这个链表:1->2->3->4->5
当 k = 2 时,应当返回: 2->1->4->3->5
当 k = 3 时,应当返回: 3->2->1->4->5

解题思路

链表题大多还是用“多指针”解决,一般都不会很难,注意不要断链就行。

  • 栈解法(空间复杂度O(k)O(k),其实不符合题意):

    • 用栈,我们把 k 个数压入栈中,然后弹出来的顺序就是翻转的!
    • 这里要注意几个问题:
      • 第一,剩下的节点个数够不够 k 个(因为不够 k 个不用翻转);
      • 第二,已经翻转的部分要与剩下链表连接起来。(不要断链)
  • 常规解法(推荐,我的实现):其实就是画图之后模拟,注意不要断链就行了。

    • 解法见下图(推荐直接看代码,更好理解)

      [LeetCode] 25、K 个一组翻转链表

参考代码

/**
 * 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) {
        ListNode* dummyHead = new ListNode(-1);
        dummyHead->next = head;
        
        ListNode* pPre = dummyHead;
        ListNode* pEnd = dummyHead;
        while(pEnd != nullptr){
            for(int i = 0; i < k; i++){
                if(pEnd != nullptr)
                    pEnd = pEnd->next;
            }
            if(pEnd == nullptr)
                break;
            
            ListNode* pStart = pPre->next;
            ListNode* pNext = pEnd->next;
            pEnd->next = nullptr;  // 重要
            pPre->next = listReverse(pStart);
            
            pStart->next = pNext;
            pPre = pStart;
            pEnd = pStart;
        }
        
        return dummyHead->next;
    }
    
    ListNode* listReverse(ListNode* head){
        ListNode* pPre = nullptr;
        ListNode* pNode = head;
        while(pNode != nullptr){
            ListNode* pNext = pNode->next;
            
            pNode->next = pPre;
            pPre = pNode;
            pNode = pNext;
        }
        
        return pPre;
    }
    
};