1721. Swapping Nodes in a Linked List

LeetCode 1721. Swapping Nodes in a Linked List

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 thekth 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 <= 105

• 0 <= Node.val <= 100

Tags

Linked List

Solution

Perform the slow-fast pointers strategy to find the value of the kth node from the end. Swap it with the value of __ the kth node from the beginning.

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(n)$

Code

func swapNodes(head *ListNode, k int) *ListNode {
	s, f := head, head
	for i := 1; i < k; i++ {
		f = f.Next
	}
	p := f
	for f.Next != nil {
		s, f = s.Next, f.Next
	}
	s.Val, p.Val = p.Val, s.Val
	return head
}