Swapping Nodes in a Linked List

Link

https://leetcode.com/problems/swapping-nodes-in-a-linked-list/

Deadline

Apr 9, 2022

Status

Archived

Type

linked list

1721. Swapping Nodes in a Linked List

Medium

1668

Add to 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]

Constraints:

The number of nodes in the list is n.

1 <= k <= n <= 105

0 <= Node.val <= 100

풀이

은찬


var swapNodes = function(head, k) {
    let current = head;
    let p1 = k - 1;
    let p2 = 0;
    const arr = [];
    
    while(current !== null){
        arr.push(current);
        current = current.next;
    }
    
    p2 = arr.length - k;
    
    [arr[p1].val, arr[p2].val] = [arr[p2].val, arr[p1].val];
    
    return head;
};

최강코딩전사재영123


// 642 ms, faster than 30.31%
var swapNodes = function(head, k) {
    const res = head;
    
    const nodes = {};
    let idx = 0;
    
    let now = head;
    while (now) {
        idx += 1;
        nodes[idx] = now;
        now = now.next;
    }
    
    const target = idx - k + 1;
    
    [nodes[k].val, nodes[target].val] = [nodes[target].val, nodes[k].val]
    
    return res;
};