Python recursive solution - O(n)


  • 0
    G
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        # @param {ListNode} head
        # @return {ListNode}
        # 12:09
        def swapPairs(self, head):
            if not head:
                return None
    
            dummyNode = ListNode(0)
            dummyNode.next = head
            fast, slow = head, dummyNode
    
            while fast and fast.next:
                fast = fast.next
                slow.next.next = fast.next
                fast.next = slow.next
                slow.next = fast
    
                slow = slow.next.next
                fast = fast.next.next
    
            return dummyNode.next

  • 0
    C

    Good solution, here is a solution uses only one pointer:

    def swapPairs(self, head):
        dummy = p = ListNode(0)
        dummy.next = head
        while p.next and p.next.next:
            tmp = head.next
            head.next = head.next.next
            tmp.next = head
            p.next = tmp
            # p = p.next.next
            # p = tmp.next
            p = head
            head = head.next
        return dummy.next

Log in to reply
 

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