March LeetCoding Challenge 2021 — Day 14: Swapping Nodes in a Linked List

Today, we will solve the 14th problem of the March LeetCoding Challenge.

Problem Statement

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 <= 105
• 0 <= Node.val <= 100

Solution

In this problem, we have to swap the k -th node from the beginning with the k -th node from the end. This is a straight forward LinkedList problem.

Here we are using the 4 nodes.

• fast— This is the k -th node from the end
• slow — This is the k -th node from the start
• first & second — They are used for swapping (to increase readability also)

Algorithm:

• First travel k-1 nodes with the fast node. Save the fast node in the first variable.
• Now travel till the end of the list, and do fast = fast.next and slow=slow.next .
• When fast.next==null , we store the slow in the second variable. This second variable is the position k nodes before the end.
• Now swap the values of first and second node.

The code is given below.

The code can be found here

sksaikia/LeetCode

Check out my other posts on March LeetCoding Challenge 2021.

1. March LeetCoding Challenge — Day 1 — Distribute Candies
2. March LeetCoding Challenge — Day 2 — Set Mismatch
3. March LeetCoding Challenge — Day 3 — Missing Number
4. March LeetCoding Challenge — Day 4 — Intersection of Two Linked Lists
5. March LeetCoding Challenge — Day 5 — Average of Levels in Binary Tree
6. March LeetCoding Challenge — Day 6 — Short Encoding of Words
7. March LeetCoding Challenge — Day 7 — Design HashMap
8. March LeetCoding Challenge — Day 8 — Remove Palindromic Subsequences
9. March LeetCoding Challenge — Day 10 — Integer to Roman
10. March LeetCoding Challenge — Day 12 — Check If a String Contains All Binary Codes of Size K