Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list's nodes, only nodes themselves may be changed.
Constraints:
- The number of nodes in the list is in the range [0, 100].
- 0 <= Node.val <= 100
Examples:
Input: [1,2,3,4]
Output: [2,1,4,3]
Explanation: After swapping, the list becomes 2 -> 1 -> 4 -> 3
Solutions
Iterative Approach
Time: O(n)Space: O(1)
We use a dummy node to simplify the code. We initialize three pointers: prev, first, and second. We iterate through the list, swapping every two adjacent nodes.
class Solution:
def swapPairs(self, head:
ListNode) -> ListNode:
dummy = ListNode(0); dummy.next = head; prev = dummy; while prev.next and prev.next.next:
first = prev.next; second = prev.next.next; first.next = second.next; second.next = first; prev.next = second; prev = first; return dummy.nextFollow-up:
What if the linked list has an odd number of nodes?
