Description

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]

 

Constraints:

• The number of nodes in the list is n.

• 1 <= k <= n <= 105

• 0 <= Node.val <= 100

Thinking

Today, we are stepping into the linked list!

This problem mainly wants to examine how to obtain the nth node from the end of the linked list. Normally, we use the double pointers to achieve that. If you want to get the k th node from the end of the linked list, you need a pointer pointing to the head of the list, and another pointer pointing to the kth node from the beginning of the list, which is easy to get. Just iterate to the kthe node. And then move two pointers simultaneously until the latter one reaches the end of the list. Then, the first pointer now are pointing to the kth node from the end, since two pointers are always k-1 away from each other.

The linked list problems are relatively intuitive and easy to solve. This is a good practice.

Solution

​x
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapNodes(ListNode* head, int k) {
        ListNode* ptr = head;
        int counter = k-1;
        
        while(counter) {
            ptr = ptr->next;
            counter -= 1;
        }

        ListNode* first_k = ptr;
        ListNode* ptr_p = head;
        
        while(ptr->next) {
            ptr_p = ptr_p->next;
            ptr = ptr->next;
        }

        swap(first_k->val, ptr_p->val);

        return head;
    }
};

What I learned

Not much honestly. Tomorrow's daily challenge is expected to still be linked-list problem. Such problems have a bunch of tricks to solve. As long as you know them and practice them well, it should not be a problem. I think the most important part is to deeply understand such data structure and try to use it in the real life projects.