If we get the idea correctly then this question is just a combination of two general questions, first one is "Find k-th
node from the end in a linked list" and "Swap two numbers". As instead of swapping the nodes, swapping the data of the nodes is sufficient. If you are going to swap actual nodes then this is going to be a little bit more tricky. But you can try that as well to test yourself. We are going to solve this question using the above logic.
Difficulty: Medium
Jump To:
Problem Statement
Question: https://leetcode.com/problems/swapping-nodes-in-a-linked-list/
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
Explanation
So the question wants two simple things from us, first one is to find k-th
node from the beginning and k-th
node from the end in a linked list. The second thing to be done is to swap both the nodes. As it's not asked to swap the actual node with its address so we can simply just swap the values of the nodes instead of swapping the nodes.
Solution
The problem needs to be solved in the below steps:
Step 1: Point to k-th
node from the beginning.
- Point a pointer
x
to the head. - Move the pointer forward in the linked list until we reached
k-th
node.
Step 2: Point to k-th
node from the end.
- Point 2 pointers
y
andt
to the head. - Move pointer
t
tillk-th
node. - Now move both the pointers
y
&t
untilt
has reached the last node. - So when
t
has reached the last node,y
must have been reachedk-th
node from the end.
Step-3: Swap values of both the nodes.
As we can guess that Point 2
of Step-2
can be done in the same loop of Point 1
of Step-1
. This will save a bit of computation for us.
Implementation
C++ Code:
class Solution {
public:
ListNode* swapNodes(ListNode* head, int k) {
ListNode *x=head, *y=head, *t=head;
// Until we reach k-th node from beginning
while(k>1){
x = x->next;
t = t->next;
k--;
}
// Until pointer t reach last need
while(t->next){
y=y->next;
t=t->next;
}
// Swap values at both the nodes
int temp = x->val;
x->val = y->val;
y->val = temp;
return head;
}
};
- Time Complexity:
O(N)
, whereN
is the length oflinked list
. - Space Complexity:
O(1)
Runnable C++ code:
Top comments (1)
I used this code and modify it according to my requirement..