题解 | #链表中的节点每k个一组翻转#

链表中的节点每k个一组翻转

http://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e

思路如下: 通过链表总长度来确定翻转次数,并循环依次翻转。翻转的范围控制为k即可。

class ListNode:

def init(self, x):

self.val = x

self.next = None

代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可

@param head ListNode类

@param k int整型

@return ListNode类

class Solution: def reverseKGroup(self , head: ListNode, k: int) -> ListNode: # write code here

    #1. 空链表直接return
    if not head: return
    
    #2. 计算链表的总长度 len_list
    numHead = head
    numList = []
    while numHead:
        numList.append(numHead.val)
        numHead = numHead.next

    len_list = len(numList)
    
    #3. 通过总长度来确定翻转次数,并循环依次翻转
    #设置m和n是翻转的范围起点和终点,在这里,我们的范围为k
    m = 1
    n = k
    for _ in range(int(len_list/k)):
        
        head = self.reverseK(head, m, n)
        #进行下一组范围为k的链表翻转
        m += k
        n += k
    
    return head

#4.翻转链表(m,n)部分。不做解释。
def reverseK(self, head, m, n):
    
    N = ListNode(-1)
    N.next = head
    
    pre = N
    for _ in range(m-1):
        pre = pre.next
    
    cur = pre.next
    for _ in range(n-m):
        temp = cur.next
        cur.next = temp.next
        temp.next = pre.next
        pre.next = temp
    
    return N.next

        
        
    
    
    
全部评论

相关推荐

10-14 23:01
已编辑
中国地质大学(武汉) Java
CUG芝士圈:虽然是网上的项目,但最好还是包装一下,然后现在大部分公司都在忙校招,十月底、十一月初会好找一些。最后,boss才沟通100家,别焦虑,我去年暑假找第一段实习的时候沟通了500➕才有面试,校友加油
点赞 评论 收藏
分享
评论
1
收藏
分享
牛客网
牛客企业服务