AC Python code using two-pointers


  • 0
    H

    The idea is to locate the (k+1)th node to the end and break the linked list.

    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def rotateRight(self, head, k):
            """
            :type head: ListNode
            :type k: int
            :rtype: ListNode
            """
            if head == None:
                return None
            p1 = p2 = head
            cnt = 0
            # count list length and do k%length
            while p1 != None:   p1, cnt = p1.next, cnt+1
            k = k % cnt
            if k == 0:  return head
            # locate the (k+1)th node to the end
            for i in range(k):  p2 = p2.next
            p1 = head
            while p2.next != None:  p1, p2 = p1.next, p2.next
            # break the list at p1 (p1.next as the new head, p1 as the new end, p2 (the old end) links to old head)
            res, p1.next, p2.next = p1.next, None, head
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.