Description#
You are given the head of a linked list, and an integer k.
Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed).
Example 1:
Input: head = [1,2,3,4,5], k = 2
Output: [1,4,3,2,5]
Example 2:
Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5
Output: [7,9,6,6,8,7,3,0,9,5]
Constraints:
- The number of nodes in the list is
n. 1 <= k <= n <= 1050 <= Node.val <= 100
Solutions#
Solution 1: Two Pointers#
We can first use a fast pointer fast to find the $k$th node of the linked list, and use a pointer p to point to it. Then, we use a slow pointer slow to start from the head node of the linked list, and move both pointers forward at the same time. When the fast pointer reaches the last node of the linked list, the slow pointer slow points to the $k$th node from the end of the linked list, and we use a pointer q to point to it. At this point, we only need to swap the values of p and q.
The time complexity is $O(n)$, where $n$ is the length of the linked list. The space complexity is $O(1)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| # Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
fast = slow = head
for _ in range(k - 1):
fast = fast.next
p = fast
while fast.next:
fast, slow = fast.next, slow.next
q = slow
p.val, q.val = q.val, p.val
return head
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| /**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapNodes(ListNode head, int k) {
ListNode fast = head;
while (--k > 0) {
fast = fast.next;
}
ListNode p = fast;
ListNode slow = head;
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
ListNode q = slow;
int t = p.val;
p.val = q.val;
q.val = t;
return head;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| /**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapNodes(ListNode* head, int k) {
ListNode* fast = head;
while (--k) {
fast = fast->next;
}
ListNode* slow = head;
ListNode* p = fast;
while (fast->next) {
fast = fast->next;
slow = slow->next;
}
ListNode* q = slow;
swap(p->val, q->val);
return head;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| /**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func swapNodes(head *ListNode, k int) *ListNode {
fast := head
for ; k > 1; k-- {
fast = fast.Next
}
p := fast
slow := head
for fast.Next != nil {
fast, slow = fast.Next, slow.Next
}
q := slow
p.Val, q.Val = q.Val, p.Val
return head
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| /**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function swapNodes(head: ListNode | null, k: number): ListNode | null {
let [fast, slow] = [head, head];
while (--k) {
fast = fast.next;
}
const p = fast;
while (fast.next) {
fast = fast.next;
slow = slow.next;
}
const q = slow;
[p.val, q.val] = [q.val, p.val];
return head;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| /**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode SwapNodes(ListNode head, int k) {
ListNode fast = head;
while (--k > 0) {
fast = fast.next;
}
ListNode p = fast;
ListNode slow = head;
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
ListNode q = slow;
int t = p.val;
p.val = q.val;
q.val = t;
return head;
}
}
|
