24. Swap Nodes in Pairs

MediumLeetCode

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1

Input: head = [1,2,3,4]

Output: [2,1,4,3]

Example 2

Input: head = []

Output: []

Example 3

Input: head = [1]

Output: [1]

Example 4

Input: head = [1,2,3]

Output: [2,1,3]

Constraints:

• The number of nodes in the list is in the range [0, 100]
• 0 <= Node.val <= 100

How to solve the problem

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummyhead = ListNode(0, head)
        cur = dummyhead
        while(cur.next!= None and (cur.next).next!= None):
            # Save node1, node3
            node1 = cur.next
            node3 = ((cur.next).next).next

            # Swapping
            cur.next = (cur.next).next
            (cur.next).next = node1
            node1.next = node3

            # Move cur to new cur
            cur = (cur.next).next
        return dummyhead.next

Complexity

• Time complexity: O(n)
• Space complexity: O(1)