Swapping Nodes in a Linked List(Linked List,Two Pointers)

https://leetcode.com/problems/swapping-nodes-in-a-linked-list/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

Linked list가 시험에 나올 가능성이 농후하여, 사전에 공부좀 해본다.

Linked list야 말로 주기적으로 친하게 지내야 하는 녀석이다.

 

1. Python

애초에 ListNode의 Method에 Prev이라는 pointer를 선언하면 안되나..했는데 그건 안 되어서 좀 짜치지만 어찌어찌 풀긴 했다.

 

성적표를 보니 모범답안은 아닌 거 같다 -_-;;

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        stack = []
        while head:
            stack.append(head.val)
            head = head.next
        stack[k-1],stack[-k] = stack[-k],stack[k-1]
        dummy = ListNode()
        temp = dummy
        for i in range(len(stack)):
            temp.next = ListNode(stack[i])
            temp = temp.next
        return dummy.next

2 - Pointer로 풀 수 있는 방법이 있긴 한가 좀 더 고민중..

 

모범답안은 아래와 같다. 왜 이런 생각을 못 했지 ㅠㅠ

 

소싯적엔 빠딱 빠딱 생각해 냈던 거 같은데 머리가 넘모 굳었다리

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        cur = head
        for _ in range(k - 1):
            cur = cur.next
        
        left = cur
        right = head
        while cur.next:
            cur = cur.next
            right = right.next
        
        left.val, right.val = right.val, left.val
        return head

 

대신 이것들을 응용해 C / C++로 한 번 풀어볼 것

 

 

2. C

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void swap(int *a, int *b){
    int temp = *b;
    *b = *a;
    *a = temp;
}

struct ListNode* swapNodes(struct ListNode* head, int k) {
    struct ListNode* left = head;
    struct ListNode* right = head;

    for(int i=1;i<k;i++){
        left = left->next;
    }

    struct ListNode* temp = left;
    while(temp->next){
        temp = temp->next;
        right = right->next;
    }

    swap(&(left->val),&(right->val));
    return head;
}

 

 

3. C++

 

/**
 * 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* slow =head, *fast = head;
        while(k!=1){
            slow = slow->next;
            k--;
        }
        ListNode* temp = slow;
        while(temp->next){
            temp = temp->next;
            fast = fast->next;
        }
        swap(slow->val,fast->val);
        return head;
    }
};