[LeetCode][1721. Swapping Nodes in a Linked List] 3 Approaches: Swapping Values and Swapping Nodes with Image Explanation
By Long Luo
This article is the solution 3 Approaches: Swapping Values and Swapping Nodes with Image Explanation of Problem 1721. Swapping Nodes in a Linked List .
Here shows 3 Approaches to slove this problem: ArrayList and Two Pointers.
Intuition
Since the \(\texttt{ListNode}\) only contain values, we can just just swap the values of two nodes. It’s very easy. All we need to do is to find these two nodes and swap their values.
If we swap nodes, it will be more difficult than swap values.
ArrayList(Swapping Values)
We can use an \(\texttt{ArrayList}\) to record all the nodes of the linked list. We can just swap the values of two nodes.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 // BF List time: O(n) space: O(n)
public static ListNode swapNodes_bf_list(ListNode head, int k) {
ListNode pNode = head;
List<ListNode> nodeList = new ArrayList<>();
// store these nodes.
while (pNode != null) {
nodeList.add(pNode);
pNode = pNode.next;
}
// swap their values.
int len = nodeList.size();
int temp = nodeList.get(k - 1).val;
nodeList.get(k - 1).val = nodeList.get(len - k).val;
nodeList.get(len - k).val = temp;
return head;
}
Analysis
- Time Complexity: \(O(n)\)
- Space Complexity: \(O(n)\)