1721. Swapping Nodes in a Linked List #

Problem #

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]

Example 3:

Input: head = [1], k = 1
Output: [1]

Example 4:

Input: head = [1,2], k = 1
Output: [2,1]

Example 5:

Input: head = [1,2,3], k = 2
Output: [1,2,3]

Constraints:

• The number of nodes in the list is n.
• 1 <= k <= n <= 10^5
• 0 <= Node.val <= 100

Problem Summary #

Given the head node head of a linked list and an integer k. Return the head node of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the linked list is 1-indexed).

Solution Approach #

• Although this problem is medium, it is actually very simple. The problem asks for the values of 2 nodes in the linked list; simply find these 2 nodes first, then swap them. Querying nodes in a linked list takes O(n). Use 2 loops to find the corresponding 2 nodes, then swap their values.

Code #

package leetcode

import (
	"github.com/halfrost/leetcode-go/structures"
)

// ListNode define
type ListNode = structures.ListNode

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapNodes(head *ListNode, k int) *ListNode {
	count := 1
	var a, b *ListNode
	for node := head; node != nil; node = node.Next {
		if count == k {
			a = node
		}
		count++
	}
	length := count
	count = 1
	for node := head; node != nil; node = node.Next {
		if count == length-k {
			b = node
		}
		count++
	}
	a.Val, b.Val = b.Val, a.Val
	return head
}