Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a singly linked list node, swap each pair of nodes and return the new head.
Constraints
n ≤ 100,000 where n is the number of nodes in node
Example 1
Input
node = [0, 1, 3, 4]
Output
[1, 0, 4, 3]Example 2
Input
node = [1, 2, 3]
Output
[2, 1, 3]
Convert Linked List to List: Pairwise Linked List Swap
For most linked list problems, we can convert (copy) to a list/array, then we can easily perform the pairwise swaps. Then we convert the list/array back to a linked list:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | # class LLNode: # def __init__(self, val, next=None): # self.val = val # self.next = next class Solution: def PairwiseLinkedListSwap(self, node): data = [] while node: data.append(node.val) node = node.next for i in range(1, len(data), 2): data[i], data[i - 1] = data[i - 1], data[i] dummy = LLNode(-1) head = dummy for i in data: head.next = LLNode(i) head = head.next return dummy.next |
# class LLNode:
# def __init__(self, val, next=None):
# self.val = val
# self.next = next
class Solution:
def PairwiseLinkedListSwap(self, node):
data = []
while node:
data.append(node.val)
node = node.next
for i in range(1, len(data), 2):
data[i], data[i - 1] = data[i - 1], data[i]
dummy = LLNode(-1)
head = dummy
for i in data:
head.next = LLNode(i)
head = head.next
return dummy.nextTime and space complexity is O(N) where N is the number of the nodes in the linked list.
Swap the Values of Nodes
We can follow/walk the link list and swap the values of every two nodes.
1 2 3 4 5 6 7 8 9 10 11 | # class LLNode: # def __init__(self, val, next=None): # self.val = val # self.next = next class Solution: def PairwiseLinkedListSwap(self, node): head = node while head and head.next: head.val, head.next.val = head.next.val, head.val head = head.next.next return node |
# class LLNode:
# def __init__(self, val, next=None):
# self.val = val
# self.next = next
class Solution:
def PairwiseLinkedListSwap(self, node):
head = node
while head and head.next:
head.val, head.next.val = head.next.val, head.val
head = head.next.next
return nodeThe time complexity is O(N) and the space complexity is O(1).
Reverse the Link
We can reverse the link for every two nodes. To do this, we can first reverse the link for the first two nodes, then then recursively link to the rest.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | # class LLNode: # def __init__(self, val, next=None): # self.val = val # self.next = next class Solution: def PairwiseLinkedListSwap(self, node): if not node or not node.next: return node tail = self.solve(node.next.next) head = node.next head.next = node node.next = tail return head |
# class LLNode:
# def __init__(self, val, next=None):
# self.val = val
# self.next = next
class Solution:
def PairwiseLinkedListSwap(self, node):
if not node or not node.next:
return node
tail = self.solve(node.next.next)
head = node.next
head.next = node
node.next = tail
return headTime complexity is O(N). Space complexity is also O(N) due to recursion.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Inplace Algorithms to Remove Elements
Next Post: Teaching Kids Programming - Linked List Jumps via Recursion
