Letcode-リンクリストの問題と解答

Letcode-リンクリストの問題の難易度順に解答します.問題は、解答に従って下部で更新されます.

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)のポインタが全く分からない.(Linuxカーネルマクロ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);
}