devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法leetcode｜25. K 个一组翻转链表（rust重拳出击）_leetcode 翻转列表

作者：小丑西瓜9 | 2024-02-15 21:11:22

赞

踩

leetcode 翻转列表

文章目录

25. K 个一组翻转链表：

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

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

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

样例 1：

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

  • 1
  • 2
  • 3
  • 4
  • 5

样例 2：

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

  • 1
  • 2
  • 3
  • 4
  • 5

提示：

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

进阶：

  • 你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

分析：

  • 面对这道算法题目，二当家的陷入了沉思。
  • 利用指针做位置交换，递归或者遍历处理，直接上就行了。
  • 递归还是比较直观，简单，看代码注释，非常详细。
  • 遍历也不难，但是单向链表需要前结点来指向当前结点，所以需要一个哑结点来统一处理，手工管理内存的话，需要最后释放掉哑结点。

题解：

rust

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn reverse_k_group(mut head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
        let mut next_group_head = &mut head;
        // 查看剩余部分长度是否大于等于 k
        for _ in 0..k {
            if next_group_head.is_none() {
                // 不够k就不用翻转了
                return head;
            }
            next_group_head = &mut next_group_head.as_mut().unwrap().next;
        }
        // 递归翻转后面
        let mut new_head = Solution::reverse_k_group(next_group_head.take(), k);
        // 将前半部分逐个拼到new_head（已经翻转好的后半部分）的前面
        while head.is_some() {
            // 正在处理翻转的结点
            let node = head.as_mut().unwrap();
            // 临时存放正在处理的结点的下一个结点
            let next = node.next.take();
            // 将正在处理的结点挂在新头的前面
            node.next = new_head.take();
            // 移动指针（正在处理的结点变成已经处理好的新头结点）
            new_head = head;
            // 移动指针（临时存放正在处理的结点的下一个结点变成将要处理的结点）
            head = next;
        }
        return new_head;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45

go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    nextGroupHead := head
	// 查看剩余部分长度是否大于等于 k
	for i := 0; i < k; i++ {
		if nextGroupHead == nil {
			// 不够k就不用翻转了
			return head
		}
		nextGroupHead = nextGroupHead.Next
	}
	// 递归翻转后面
	newHead := reverseKGroup(nextGroupHead, k)
	// 将前半部分逐个拼到new_head（已经翻转好的后半部分）的前面
	for i := 0; i < k; i++ {
		// 临时存放正在处理的结点的下一个结点
		next := head.Next
		// 将正在处理的结点挂在新头的前面
		head.Next = newHead
		// 移动指针（正在处理的结点变成已经处理好的新头结点）
		newHead = head
		// 移动指针（临时存放正在处理的结点的下一个结点变成将要处理的结点）
		head = next
	}
	return newHead
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

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 *nextGroupHead = head;
        // 查看剩余部分长度是否大于等于 k
        for (int i = 0; i < k; ++i) {
            if (nextGroupHead == nullptr) {
                // 不够k就不用翻转了
                return head;
            }
            nextGroupHead = nextGroupHead->next;
        }
        // 递归翻转后面
        ListNode *newHead = reverseKGroup(nextGroupHead, k);
        // 将前半部分逐个拼到new_head（已经翻转好的后半部分）的前面
        for (int i = 0; i < k; ++i) {
            // 临时存放正在处理的结点的下一个结点
            ListNode *next = head->next;
            // 将正在处理的结点挂在新头的前面
            head->next = newHead;
            // 移动指针（正在处理的结点变成已经处理好的新头结点）
            newHead = head;
            // 移动指针（临时存放正在处理的结点的下一个结点变成将要处理的结点）
            head = next;
        }
        return newHead;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38

c

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseKGroup(struct ListNode* head, int k){
    struct ListNode *nextGroupHead = head;
    // 查看剩余部分长度是否大于等于 k
    for (int i = 0; i < k; ++i) {
        if (nextGroupHead == NULL) {
            // 不够k就不用翻转了
            return head;
        }
        nextGroupHead = nextGroupHead->next;
    }
    // 递归翻转后面
    struct ListNode *newHead = reverseKGroup(nextGroupHead, k);
    // 将前半部分逐个拼到new_head（已经翻转好的后半部分）的前面
    for (int i = 0; i < k; ++i) {
        // 临时存放正在处理的结点的下一个结点
        struct ListNode *next = head->next;
        // 将正在处理的结点挂在新头的前面
        head->next = newHead;
        // 移动指针（正在处理的结点变成已经处理好的新头结点）
        newHead = head;
        // 移动指针（临时存放正在处理的结点的下一个结点变成将要处理的结点）
        head = next;
    }
    return newHead;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34

python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        next_group_head = head
        # 查看剩余部分长度是否大于等于 k
        for _ in range(k):
            if next_group_head is None:
                # 不够k就不用翻转了
                return head
            next_group_head = next_group_head.next
        # 递归翻转后面
        new_head = self.reverseKGroup(next_group_head, k)
        # 将前半部分逐个拼到new_head（已经翻转好的后半部分）的前面
        for _ in range(k):
            # 临时存放正在处理的结点的下一个结点
            next = head.next
            # 将正在处理的结点挂在新头的前面
            head.next = new_head
            # 移动指针（正在处理的结点变成已经处理好的新头结点）
            new_head = head
            # 移动指针（临时存放正在处理的结点的下一个结点变成将要处理的结点）
            head = next
        return new_head


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

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) {
        ListNode nextGroupHead = head;
        // 查看剩余部分长度是否大于等于 k
        for (int i = 0; i < k; ++i) {
            if (nextGroupHead == null) {
                // 不够k就不用翻转了
                return head;
            }
            nextGroupHead = nextGroupHead.next;
        }
        // 递归翻转后面
        ListNode newHead = reverseKGroup(nextGroupHead, k);
        // 将前半部分逐个拼到new_head（已经翻转好的后半部分）的前面
        for (int i = 0; i < k; ++i) {
            // 临时存放正在处理的结点的下一个结点
            ListNode next = head.next;
            // 将正在处理的结点挂在新头的前面
            head.next = newHead;
            // 移动指针（正在处理的结点变成已经处理好的新头结点）
            newHead = head;
            // 移动指针（临时存放正在处理的结点的下一个结点变成将要处理的结点）
            head = next;
        }
        return newHead;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
/**
 * 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) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;

        while (pre.next != null) {
            ListNode tail = pre;
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail.next;
                if (tail == null) {
                    return dummy.next;
                }
            }
            // 指针后移
            pre = reverse(pre, tail);
        }

        return dummy.next;
    }

    private ListNode reverse(ListNode pre, ListNode tail) {
        ListNode newTail = pre.next;
        ListNode newHead = tail.next;
        ListNode head    = newTail;
        while (newHead != tail) {
            ListNode next = head.next;
            head.next = newHead;
            newHead = head;
            head = next;
        }
        pre.next = newHead;
        return newTail;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号