Python solution only go through LL once


  • 1
    U

    This one requires extra memory space to store refs to all nodes, but no need to iterate through it again.

    class Solution(object):
        def rotateRight(self, head, k):
            """
            :type head: ListNode
            :type k: int
            :rtype: ListNode
            """
            if head is None:
                return None
            if head.next is None:
                return head
            nodes = []
            p = ListNode(None)
            p.next = head
            q = p
            while q.next is not None:
                q = q.next
                nodes.append(q)
            k %= len(nodes)
            if k == 0:
                return head
            newHead = nodes[-k]
            nodes[-k - 1].next = None
            nodes[-1].next = head
            return newHead
    

Log in to reply
 

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