美文网首页
Q25 - Hard - k个一组翻转链表

Q25 - Hard - k个一组翻转链表

作者: 1f872d1e3817 | 来源:发表于2019-02-13 00:15 被阅读0次

    给出一个链表,每 k 个节点一组进行翻转,并返回翻转后的链表。

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

    示例 :

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

    当 k = 2 时,应当返回: 2->1->4->3->5

    当 k = 3 时,应当返回: 3->2->1->4->5

    说明 :

    你的算法只能使用常数的额外空间。
    你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

    
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        def reverse(self, head, k):
            p = head
            for i in range(k):  # 先检验够不够数
                p = p.next
                if p is None:
                    return None
            p = head.next.next
            last = head.next
            for i in range(k - 1):  # 翻转
                last.next = p.next
                p.next = head.next
                head.next = p
                p = last.next
            return last
            
        def reverseKGroup(self, head, k):
            """
            :type head: ListNode
            :type k: int
            :rtype: ListNode
            """
            if k < 2:
                return head
            dummy = ListNode(0)
            dummy.next = head
            p = dummy
            while p is not None:
                p = self.reverse(p, k)
            return last.next
    

    翻转

    翻转的思想是,把p一个挨一个的拎到head后面

    比如1 2 3 4 5,k = 3 加上dummy为 0 1 2 3 4 5

    第1趟循环: 0 1 2 3 4 5

    head --> 0, last --> 1,p --> 2
    把2拎到0的后面,变成0 2 1 3 4 5

    第2趟循环:0 2 1 3 4 5

    head --> 0, last --> 1,p --> 3
    把3拎到0的后面,变成0 3 2 1 4 5

    第3趟循环:0 3 2 1 4 5

    head --> 0, last --> 1,p --> 4
    把4拎到0的后面,变成0 4 3 2 1 5

    循环了k-1次即3次,循环退出

    最后得 4 3 2 1 5

    相关文章

      网友评论

          本文标题:Q25 - Hard - k个一组翻转链表

          本文链接:https://www.haomeiwen.com/subject/qpnleqtx.html