LeetCode25. K 个一组翻转链表🌟🌟🌟困难

算法系统课免费

问题描述

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

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

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

提示：

链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

代码实现

Java

/**
 * 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) {
        // 1-》2-〉3-》4-〉5。K = 2;
        ListNode temp = head;
        //1-》2，    3-〉4-》4
        for(int i = 1; temp != null && i < k; i++ ){
            temp = temp.next;
        }

        if(temp == null){
            return head;
        }
        // t指向第二部分:t->3->4->5->null.  head->1->2->null;
        ListNode t = temp.next;
        temp.next = null;
        // newhead->2->1->null;
        ListNode newHead = reverseList(head);
        //newTemp->3->4->5->null
        ListNode newTemp = reverseKGroup(t, k);
        // 拼接
        head.next = newTemp;
        return newHead;


    }

    ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode result = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return result;
    }
}

Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        # 1-》2-〉3-》4-〉5。K = 2;
        temp = head
        #1-》2，    3-〉4-》4
        for i in range(1, k):
            if temp is None:
                return head
            temp = temp.next

        if temp is None:
            return head
        # t指向第二部分:t->3->4->5->null.  head->1->2->null;
        t = temp.next
        temp.next = None
        # newhead->2->1->null;
        newHead = self.reverseList(head)
        #newTemp->3->4->5->null
        newTemp = self.reverseKGroup(t, k)
        # 拼接
        head.next = newTemp
        return newHead


    def reverseList(self, head):
        if head is None or head.next is None:
            return head
        result = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return result

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* temp = head;
        for(int i = 1; temp != nullptr && i < k; i++ ){
            temp = temp->next;
        }

        if(temp == nullptr){
            return head;
        }

        ListNode* t = temp->next;
        temp->next = nullptr;

        ListNode* newHead = reverseList(head);

        ListNode* newTemp = reverseKGroup(t, k);

        head->next = newTemp;
        return newHead;
    }

    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr)
            return head;
        ListNode* result = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return result;
    }
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    temp := head
    for i := 1; temp != nil && i < k; i++ {
        temp = temp.Next
    }

    if temp == nil {
        return head
    }

    t := temp.Next
    temp.Next = nil

    newHead := reverseList(head)

    newTemp := reverseKGroup(t, k)

    head.Next = newTemp
    return newHead
}

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    result := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return result
}

ListNode dummy = new ListNode(0, head), p0 = dummy; ListNode pre = null, cur = head; for (; n >= k; n -= k) { for (int i = 0; i < k; ++i) { // 同 92 题 ListNode nxt = cur.next; cur.next = pre; // 每次循环只修改一个 next，方便大家理解 pre = cur; cur = nxt; } // 见视频 ListNode nxt = p0.next; p0.next.next = cur; p0.next = pre; p0 = nxt; } return dummy.next; }

ListNode* reverseKGroup(ListNode* head, int k) { ListNode*dummyHead=new ListNode(0); dummyHead->next=head; ListNode*pre=dummyHead; while(head){ ListNode*tail=pre; //检查剩余是否≥k，没有的话则保持原来顺序 for(int i=0;i<k;i++){ tail=tail->next; if(tail==nullptr){ return dummyHead->next; } } ListNode*tmp=tail->next; //翻转链表 tie(head,tail)=reverseList(head,tail); //重新接回去 pre->next=head; tail->next=tmp; pre=tail; head=tail->next; } return dummyHead->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; } * } */ // 时间复杂度：O( n ~ n^2) // 空间复杂度：O(1) class Solution { public ListNode reverseKGroup(ListNode head, int k) { //函数目的：递归k位反转 //终止条件 ListNode temp = head; for(int i = 1; i < k; i++) { if(temp != null) { temp = temp.next; } else { return head; } } if(temp == null) return head; ListNode r = temp.next; temp.next = null; //关系式 ListNode newHead = reverseList(head); ListNode newTemp = reverseKGroup(r, k); head.next = newTemp; //反转使得首位排末尾 return newHead; } ListNode reverseList(ListNode head) { //函数目的：反转链表 //终止条件 if(head == null || head.next == null) { return head; } //关系式 ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; } }

class Solution { public ListNode reverseKGroup(ListNode head, int k) { // head->1->2->3->4->5 k=2 ListNode temp = head; // 定位需要反转的最后一个节点 for (int i = 1; temp != null && i < k; i ++) { temp = temp.next; } // 不足k个，不需要反转 if (temp == null) { return head; } // 切分 // head->1->2->null t->3->4->5->null ListNode t = temp.next; temp.next = null; // 开始反转 newHead->2->1->null ListNode newHead = reverseList(head); // newTemp->3->4->5->null ListNode newTemp = reverseKGroup(t, k); // 拼接 head.next = newTemp; return newHead; } // 反转链表 ListNode reverseList(ListNode head) { // 链表为空或只有一个节点 if (head == null || head.next == null) { return head; } // 关系式 ListNode res = reverseList(head.next); head.next.next = head; head.next = null; return res; } }

/** * 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(head == null || head.next == null) { return head; } ListNode tmp = head; for(int i = 1; i < k && tmp != null; i ++) { tmp = tmp.next; } if(tmp == null) { return head; } ListNode t = tmp.next; tmp.next = null; ListNode prefixHead = reverseList(head); ListNode suffixHead = reverseKGroup(t,k); head.next = suffixHead; return prefixHead; } ListNode reverseList(ListNode head) { if(head == null || head.next == null) { return head; } ListNode cur = head; ListNode pre = null; while(cur != null) { ListNode tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } return pre; } }

class Solution { public ListNode reverseKGroup(ListNode head, int k) { //判断链表长度是否大于等于k ListNode temp = head; for(int i = 1; i < k && temp != null; i++){ temp = temp.next; } if(temp == null) return head;//此时链表长度小于k，无需反转，直接返回head //断开链表，t指向后面的链表 ListNode t = temp.next; temp.next = null; ListNode newHead = reverse(head);//反转以head为头节点的前K个元素组成的链表 ListNode khead = reverseKGroup(t, k);//递归反转剩余链表 head.next = khead;//此时head是以newHead为头结点的链表的队尾节点 return newHead; } //递归法反转链表 public ListNode reverse(ListNode head){ if(head == null || head.next == null){ return head; } ListNode last = reverse(head.next); head.next.next = head; head.next = null; return last; } }

发表回复取消回复

后才能评论

翰林猿永久会员 2024年7月12日下午4:05

class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
int n = 0;
for (ListNode cur = head; cur != null; cur = cur.next)
++n; // 统计节点个数

}

Yuki 永久会员 2024年1月30日下午4:14

打卡，但是没有ac，明天再写一遍
class Solution {
public:
//翻转链表后，返回新的头结点和尾结点
pair<ListNode,ListNode>reverseList(ListNodehead,ListNodetail){
ListNodepre=nullptr;
ListNodecur=head;
while(cur->next!=nullptr){
ListNode*tmp=cur->next;
cur->next=pre;
pre=cur;
cur=tmp;
}
return {tail,head};
}

};

uu 永久会员 2023年9月20日下午3:34

思路和视频一样，但是reverseKGroup的递归关系式写地很乱写不出来

泡芙永久会员 2023年9月5日下午5:42

递归

Time：O(n)
Space：O(n/k + k)，栈调用深度
ListNode newHead = reverseList(head); k次

ListNode newTemp = reverseKGroup(t, k); n/k 次

AD钙奶普通 2023年8月31日下午5:45

打卡

阿尚普通 2023年8月17日下午2:12

帅气的冬瓜普通 2023年6月28日下午4:46

打卡

登录以回复

问题描述

代码实现

Java

Python

C++

Go

发表回复 取消回复

评论(7)

递归

付款后无法显示下载地址或者无法查看内容？

发表回复取消回复