Reference: LeetCode
Difficulty: Medium
Problem
Given a linked list, swap every two adjacent nodes and return its head.
Note: You may not
modify the values in the list’s nodes, only nodes itself may be changed.
Example:
1 | Given 1->2->3->4, you should return the list as 2->1->4->3. |
Analysis
Test Case:
1 | // 1 |
Recursion
1 | public ListNode swapPairs(ListNode head) { |
Time: $O(N)$
Space: $O(N)$
Iteration
Note: Use this template for most iterative methods:
1 | ListNode dummy = new ListNode(0); |
If I use p.next
as a left-value in the block code, I have to indicate in the while condition that p.next != null
. And usually, p != null
and p.next != null
are together.
Update prev
before updating p
.
1 | public ListNode swapPairs(ListNode head) { |
Time: $O(N)$
Space: $O(1)$