Leetcode -Linked List 문제 및 풀이

Leetcode - linked list 문제 난이도 순서대로 풀기. 문제는 푸는대로 하단에 업데이트.

1290. Convert Binary Number in a Linked List to Integer

링크드 리스트의 값이 0또는 1일때 주어진 리스트가 이진수로 표현하는 값을 구하기
Input: head = [1,0,1] Output: 5

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
int getDecimalValue(struct ListNode* head){
    struct ListNode *n = head;
    int ret = 0;
    for (; n != NULL; n = n->next) {
        ret <<= 1;
        ret = ret | n->val;
    } 
    return ret;
}

876. Middle of the Linked List

링크드 리스트의 head포인터가 주어지고, 리스트의 중간노드를 리턴하기

Input: head = [1,2,3,4,5] Output: [3,4,5]
Input: head = [1,2,3,4,5,6] Output: [4,5,6]

https://leetcode.com/problems/middle-of-the-linked-list

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* n = head;
    int nr_list = 0;
    int target = 0;
    
    for (;n != NULL; n = n->next)
       nr_list++; 
    for (n = head; n != NULL; n = n->next)
        if (++target == (nr_list / 2 + 1))
            break;
    return n;
}

237. Delete Node in a Linked List

노드 삭제연산을 구현하는데 주어지는 매개변수가 head포인터가 아니라 해당 노드포인터 하나임.
https://leetcode.com/problems/delete-node-in-a-linked-list/

전통적인 노드 삭제는 (4) 의 next를 (1)으로 연결하면 되는데 이 문제에서는 (4)의 포인터를 알 방법이 전혀없다.(리눅스 커널 매크로인 container_of()를 사용하면 되려나?) 그래서 의외로 고민을 많이 했는데 해결방안은 간단하게도 삭제 대상 노드를 지우는게 아니라, 그다음 노드의 값으로 바꾸는것. 이런 삭제 방법을 처음봐서 신선했다.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void deleteNode(struct ListNode* node) {
    struct ListNode *n = node->next;
    node->val = n->val;
    node->next = n->next;
    free(n);
}