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
LeetCode
I have been solving Leetcode problems for around a year or so. Suddenly I have developed a passion of writing tutorials for these problems. I am starting with Leetcode problem, in future I will try to make tutorials on Spring,Android,Java,Algorithms and many more.
Follow me on medium - https://sourav-saikia.medium.com
Follow me on dev.to - https://dev.to/sksaikia
Follow me on twitter - https://twitter.com/sourav__saikia
Connect on Linkedin - www.linkedin.com/in/sourav-kumar-saikia
The following table contains all the problems with their respective solution tutorials. I will try to add more articles to it soon.
| Problem Name | Problem No | Article Links |
|---|---|---|
| Contains Duplicate | 217 | https://sourav-saikia.medium.com/leetcode-217-contains-duplicate-solution-36f48793bce0 |
| Jewels and Stones | 771 | https://sourav-saikia.medium.com/leetcode-771-jewels-and-stones-e35a368fc37 |
March LeetCoding Challenge
| Problem Name | Problem No | Article Links |
|---|---|---|
| Distribute Candies | 575 | https://medium.com/dev-genius/march-leetcoding-challenge-2021-problem-1-distribute-candies-f37f66ea7ee9 |
| Set Mismatch | 645 | https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-2-set-mismatch-4abd5ee491c9 |
| Missing Number | 268 | https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-3-missing-number-ae8ee45a58cb |
| Intersection of Two Linked Lists | 160 | https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-4-intersection-of-two-linked-lists-a775449b5563 |
| Average of Levels in Binary Tree | 637 | https://medium.com/dev-genius/march-leetcoding-challenge-2021-day-5-average-of-levels-in-binary-tree-ac886b2b42e8 |
| Short Encoding of Words | 820 | https://sourav-saikia.medium.com/march-leetcoding-challenge-2021-day-6-short-encoding-of-words-7fed4bfae557 |
| Remove Palindromic Subsequences | 1332 |
Check out my other posts on March LeetCoding Challenge 2021.
March LeetCoding Challenge — Day 4 — Intersection of Two Linked Lists
March LeetCoding Challenge — Day 5 — Average of Levels in Binary Tree
March LeetCoding Challenge — Day 6 — Short Encoding of Words
March LeetCoding Challenge — Day 8 — Remove Palindromic Subsequences
March LeetCoding Challenge — Day 12 — Check If a String Contains All Binary Codes of Size K
Top comments (0)