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:
Two passes. First pass, find the length of the list. Second pass, record the k-th and n-k+1-th node.
Once done swap their values.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution { public: ListNode* swapNodes(ListNode* head, int k) { int l = 0; ListNode* cur = head; while (cur) { cur = cur->next; ++l; } cur = head; ListNode* n1 = nullptr; ListNode* n2 = nullptr; for (int i = 1; i <= l; ++i, cur = cur->next) { if (i == k) n1 = cur; if (i == l - k + 1) n2 = cur; } swap(n1->val, n2->val); return head; } }; |