【python-leetcode25-翻转链表】K 个一组翻转链表

发布时间：2020-12-20 09:54:38 所属栏目：Python 来源：网络整理

导读：问题描述：给你一个链表，每?k?个节点一组进行翻转，请你返回翻转后的链表。 k?是一个正整数，它的值小于或等于链表的长度。如果节点总数不是?k?的整数倍，那么请将最后剩余的节点保持原有顺序。示例 : 给定这个链表：1-2-3-4-5 当?k?= 2 时，应当返回: 2

问题描述：

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

k?是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是?k?的整数倍，那么请将最后剩余的节点保持原有顺序。

示例 :

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

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

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

说明 :

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

方法一：利用栈（不过空间复杂度为O（k））

过程：

一次循环之后：

第二次循环过后：

第三次循环：由于tmp==None，此时count=，因此直接将p.next指向head。最后返回newhead.next即可。

代码：

class ListNode:
    def __init__(self,x):
        self.val=x
        self.next=None
n1=ListNode(1)
n2=ListNode(2)
n3=ListNode(3)
n4=ListNode(4)
n5=ListNode(5)
n6=ListNode(6)
n7=ListNode(7)
n1.next=n2;n2.next=n3;n3.next=n4;n4.next=n5

def printListNode(head):
    while head != None:
        print(head.val)
        head=head.next
#printListNode(n1)

 Solution:
     reverseKGroup(self,head,k):
        newhead = ListNode(0)
        p = newhead
        while True:
            count = k 
            stack = []
            tmp = head
            while count and tmp:
                stack.append(tmp)
                tmp = tmp.next
                count -= 1
            if count : 
                p.next = head
                break
             stack:
                p.next = stack.pop()
                p = p.next
            head = tmp
        
        return newhead.next
                
            

s=Solution()
t=s.reverseKGroup(n1,2)
printListNode(t)

方法二：尾插法

初始化：

进入第一次循环：

进入第二次循环：

依次类推。

再比如:[1,2,3,4,5,6,7]，k=3，过程也就是：

[2,1,7]

[3,7]?

[3,7]

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

def reverseKGroup(self,head: ListNode,k: int) -> ListNode:
        newhead= ListNode(0)
        newhead.next = head
        pre = newhead
        tail = k
             tail:
                count -= 1
                tail = tail.next
            if not tail: break
            head = pre.next
            while pre.next != tail:
                cur = pre.next  获取下一个元素
                 pre与cur.next连接起来,此时cur(孤单)掉了出来
                pre.next = cur.next 
                cur.next = tail.next  和剩余的链表连接起来
                tail.next = cur 插在tail后面
             改变 pre tail 的值
            pre = head 
            tail = head
        return newhead.next

方法三：递归，理解不了

 head
        count = 0
        while cur and count!= k:
            cur = cur.next
            count += 1
        if count == self.reverseKGroup(cur,k)
            print("cur.val=",cur.val)
             count:
                head.val= head.next
                head.next = cur
                cur = head
                head = tmp
                count -= 1 cur   
        return head

代码来源：

作者：powcai
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/solution/kge-yi-zu-fan-zhuan-lian-biao-by-powcai/
来源：力扣（LeetCode）

为了加深理解，图为自己所作。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!