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;
}

slow/fast pointer 방법

두가지 종류의 풀이법이 있다.

• 1. while (fast && fast->next) {

    ListNode* middleNode(ListNode* head) {
        ListNode *slow = head;
        ListNode *fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow; // both of even and odd case
    }

짝수의 경우는 slow는 중간에서 하나 이후 노드리턴

노드 갯수가 
짝수인경우 루프의 종료조건 
         1 2 
           ^ |
         1 2 3 4
             ^   |
         1 2 3 4 5 6      end of even case:
               ^     |     -> fast is NULL
홀수인경우 루프의 종료조건
         1
         ^|
         1 2 3
           ^ |
         1 2 3 4 5        end of odd case
             ^   |        -> fast->next is NULL

• 2. while (fast->next && fast->next->next)

    ListNode* middleNode2(ListNode* head) {
        ListNode *slow = head;
        ListNode *fast = head;

        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        if (!fast->next) // for odd case
            return slow;
        return slow->next; // for even case
    }
};

짝수의 경우는 slow는 중간에서 하나 이전 노드리턴

 노드 갯수가 
짝수인경우 루프의 종료조건 
         1 2
         ^|
         1 2 3 4
           ^ |
         1 2 3 4 5 6      for even
             ^   |     -> fast->next->next is NULL
홀수인경우 루프의 종료조건
         1
         ^|
         1 2 3
           ^ |
         
         1 2 3 4 5        for odd
             ^   |     -> fast->next is NULL

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);
}

83. Remove Duplicates from Sorted List

중복된 노드를 제거하기

Input: head = [1,1,2,3,3]
Output: [1,2,3]

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *prev = NULL;
        ListNode *cur = head;
        ListNode *newhead = head;
        
        for (; cur != NULL; cur = cur->next) {
            if (prev && prev->val == cur->val)
                prev->next = cur->next;
            else
                prev = cur;
        }
        return newhead;
    }
};

203. Remove Linked List Elements

문제

링크드 리스트에서 val값을 가진 노드를 모두 제거하라

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

https://leetcode.com/problems/remove-linked-list-elements/

해결

노드가 헤드인경우와 아닌경우를 구분해야함.

struct ListNode *removeElements(struct ListNode *head, int val){
    struct ListNode *node = head;
    struct ListNode *prev = NULL;
    
    while (node != NULL) {
        if (node ->val != val) {
            prev = node;
            node = node->next;
            continue;
        }
        if (node == head) {
            head = node->next;
            prev = node;
            node = node->next;
        } else {
            prev->next = node->next;
            node = node->next;
        }
    }    
    return head;
}

148. Sort List

문제

주어진 링크드 리스트를 오름차순 정렬하라.

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

해결 O(nlogn) / O(n)

각 노드를 heap에 넣고 하나씩 pop하면서 새로 링크르 리스트를 생성.

• 기존 노드를 재조합해서 새 링크드 리스트를 생성할때는 마지막 노드부터 시작해서 head로 만들어야함. 아래 코드 참고

        while (!pq.empty() ) {
            node = pq.top();
            node->next = newhead;
            newhead = node;
            pq.pop();
        }

• 따라서 heap은 max heap이어야함. 큰 값의 노드부터 링크의 마지막에 생성되니.

class myCompare {
public:
    bool operator() (const ListNode *p1, const ListNode *p2) {
        return p1->val < p2->val;
    }
};

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        priority_queue<ListNode*, vector<ListNode*>, myCompare> pq;
        ListNode *node = head;
        while (node != NULL) {
            pq.push(node);
            node = node->next;
        }
        ListNode *newhead = NULL;
        while (!pq.empty() ) {
            node = pq.top();
            node->next = newhead;
            newhead = node;
            pq.pop();
        }
        return newhead;
    }
};

해결 - merge sort방법 O(nlogn)

Divide and Conquer 전략으로 푸는 방법.
중간노드를 찾아 두개의 리스트로 나눈뒤 각각 정렬하고 그 두개를 다시 합치면서 정렬.
return merge_list(sortList(head), sortList(r_head));

class Solution {
    ListNode *merge_list(ListNode *left, ListNode *right) {
        ListNode *newhead = new ListNode;
        ListNode *prev = newhead;
        
        while (left && right) {
            if (left->val < right->val) {
                prev->next = left;
                left = left->next;
            } else {
                prev->next = right;
                right = right->next;
            }
            prev = prev->next;
        }
        prev->next = (left) ? left : right; // node is not null
        return newhead->next;
    }
public:
    ListNode *sortList(ListNode *head) {
        if (!head || !head->next)
            return head;
        ListNode *r_head = head;
        ListNode *slow = head;
        ListNode *fast = head;
        
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        r_head = slow->next;
        slow->next = NULL;
        
        return merge_list(sortList(head), sortList(r_head));
    }
};

206. Reverse Linked List

문제

링크드 리스트를 reverse하라.

https://leetcode.com/problems/reverse-linked-list/

해결 O(n) / O(1)

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode *node = head, *prev = NULL, *tmp = head;
    for (; node != NULL; prev = node, node = tmp) {
        tmp = node->next;
        node->next = prev;
    }
    return prev;
}

92. Reverse Linked List II

문제

오름차순 정렬된 링크드리스트와 노드의 위치 인덱스 left, right가 주어질때, left에서 right까지의 범위를 reverse해라.

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

해결

아래의 쟁점을 해결 및 구현해야한다.

• 범위내의 리스트를 reverse 하기
• 그뒤 범위 밖의 prev_left, 와 next_head를 연결하기
• 주어진 left위치가 링크드리스트의 head위치일때 처리하기.

struct ListNode* reverse_list(struct ListNode* head, struct ListNode *next_right)
{
    struct ListNode *node = head, *prev = next_right, *tmp = head;
    for (; node != next_right; prev = node, node = tmp) {
        tmp = node->next;
        node->next = prev;
    }
    return prev;
}

기존의 reverse연산과 동일하고, 다만 prev 노드가 NULL이 아닌 next_right 로 초기화 한다는점이 다르다. 범위의 시작노드는 node->next 가 next_right를 가리켜야 하기 때문. 기존 reverse연산 참고: [C] Single Linked List 구현

struct ListNode* reverseBetween(struct ListNode* head, int left, int right){
    struct ListNode *prev_left = head;
    struct ListNode *next_right = head;
    struct ListNode *new_head = malloc(sizeof(struct ListNode));
    new_head->next = head;
    struct ListNode *prev = new_head, *node = new_head;
    int node_cnt = 0;
    
    for (;node != NULL; prev = node, node = node->next) {
        if (node_cnt == left)
            prev_left = prev;
        if (node_cnt == right)
            next_right = node->next;
        node_cnt++;
    }
    prev_left->next = reverse_list(prev_left->next, next_right);
    return new_head->next;
}

그 뒤에 prev_left->next에 reverse된 리스트를 할당한다.

141. Linked List Cycle

문제

배열이 주어지고 각 링크드리스트 노드를 나타낸다. pos는 마지막 노드의 next 포인터 위치를 나타낸다. -1 이면 next 포인터는 NULL이다. 이 링크드리스트가 사이클을 갖는지 아닌지 판단하라.

Input: head = [3,2,0,-4], pos = 1
Output: true

해결 O(n) / O(n)

굉장히 흥미로운 문제였다. 노드를 순회하면서 노드의 포인터값을 해시테이블의 key로해서 빈도를 저장했다.
답은 맞았는데, 솔직히 이렇게 해도 되는건지 모르겠다... 포인터주소의 hash collision처리도 안되어있고.. 다음에 다른 방법으로 한번 더 풀어봐야할듯!

1. Constraints
 - single node can be cycle?
 - how many node? 0 ~ 10000
 - the valses can be duplicated? 
 - if pos == -1, what is tail->next? NULL?
2. Ideas
3. TestCases

#define HSIZE 200001
bool hasCycle(struct ListNode *head) {
    struct ListNode *node = head;
    struct ListNode *table[HSIZE] = {0};
    memset(table, 0, sizeof(struct ListNode *) * HSIZE);
    
    for (;node != NULL; node = node->next) {
        if (table[(int)node % HSIZE])
            return true;
        table[(int)node % HSIZE]++;
    }
    return false;
}

해결 O(n) / O(1)

추가 메모리를 사용하지 않고 공간복잡도를 O(1)푸는 방법.
서로 속도가 다른 two pointer기법이다. 한칸씩 이동하는 slow와 두칸씩 이동하는 fast포인터로 루프를 돌리다보면 사이클이 있을때, 이 둘은 언젠가는 만난다. 아주 신박한 방법! (참고로 풀이가 링크드 리스트의 중간노드 찾는것과 동일하다. 루프 종료후 slow가 중간노드)

bool hasCycle(struct ListNode *head) {
    if (head == NULL)
        return false;
    struct ListNode *slow = head, *fast = head->next;
    while (fast != NULL && fast->next != NULL) {
        if (slow == fast)
            return true;
        slow = slow->next;
        fast = fast->next->next;
    }
    return false;
}

142. Linked List Cycle II

문제

링크드 리스트의 head만 주어진다. 만약 리스트에 사이클이 존재한다면 사이클이 시작되는 노드를 리턴하라. 사이클이 없다면 NULL리턴

https://leetcode.com/problems/linked-list-cycle-ii/

유사문제

Leetcode - 141. Linked List Cycle

해결

해시 테이블 사용

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_map<ListNode *, int> table;
        while (head) {
            if (table[head])
                return head;
            table[head]++;
            head = head->next;
        }
        return NULL;
    }
};

86. Partition List

문제

링크드 리스트와 값이 주어진다. 주어진 값 x를 기준으로 작은 값은 리스트의 왼쪽에 큰값은 그 뒤로 배치하라. 단 기존 리스트의 상대적인 순서는 유지되어야한다.

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

해결

x보다 작은값들의 리스트, x보다 같거나 큰 값들의 리스트 두개를 만들고 마지막에 합친다. 이를 위해 각각의 리스트에 head, tail를 가리키는 포인터가 필요.

두 개의 리스트를 만드는것까지는 금방했는데, 마지막에 합칠때 이런 저런 조건처리가 필요해 오래걸림.
총 3가지 경우의수를 처리해야함. 그리고 리스트가 비어있을 경우(이건 3으로 처리됨)
1. x값이 리스트의 모든 값보다 작은 경우
2. x값이 리스트의 모든 값보다 큰 경우
3. x값이 리스트 값 사이에 있는 경우

struct ListNode *partition(struct ListNode *head, int x){
    struct ListNode *l_head = NULL, *l_tail = head;
    struct ListNode *r_head = NULL, *r_tail = head;
    struct ListNode *node = head;
    
    for (;node != NULL; node = node->next) {
        if (node->val < x) {
            if (l_head == NULL) {
                l_head = node;
                l_tail = l_head;
            } else {
                l_tail->next = node;
                l_tail = node;
            }
        } else {
            if (r_head == NULL) {
                r_head = node;
                r_tail = node;
            } else {
                r_tail->next = node;
                r_tail = node;
            }
        }
    }
    /* x is less than all of nodes */
    if (l_head == NULL && r_head) {
        if (r_tail)
            r_tail->next = NULL;
        return r_head;
    }
    /* x is greater than all of nodes */
    if (r_head == NULL && l_head) {
        return l_head;
    }
    /* x is between the nodes */
    if (r_tail)
        r_tail->next = NULL;
    if (l_tail)
        l_tail->next = r_head;
    return l_head;
}

61. Rotate List

문제

주어진 링크드 리스트를 k 번 rotate시켜라.

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

해결 O(N^2)

한번 rotate하는건 쉽다. 링크드리스트의 맨 마지막 노드 (node), 그리고 직전노드 prev라고 할때, 아래와 같이 하면된다.

        prev->next = NULL;
        node->next = head;
        head = node;

이걸 k 번반복. 총 시간복잡도는 O(N^2)가 된다.
역시나 TLE 발생 (12 / 231 test cases passed.)

struct ListNode* rotateRight(struct ListNode* head, int k){
    struct ListNode *node = head, *prev = NULL;
    for (int i = 0; i < k; i++) {
        for (; node && node->next; prev = node, node = node->next)
            ;
        if (!prev)
            break;
        prev->next = NULL;
        node->next = head;
        head = node;
    }
    return head;
}

해결 O(N)

생각해보면 전체 k번 rotate할 필요가 없다. 참고로 k가 될수 있는 값은 매우 크다(0 <= k <= 2 * 10^9). 리스트의 크기 이하 번만 rotate할수 있게 계산이 가능하다. head_pos = list_size - (k % list_size); 이렇게 새로운 head가 될 노드의 위치를 계산할 수 있다.

그리고 첫번째 해결방법처럼 맨 마지막 노드tail을 찾아서 이전 head를 가리키게 하면 된다.

    prev->next = NULL;
    tail->next = head;
    head = node;

결과는 100% faster 가 나왔음.

struct ListNode* rotateRight(struct ListNode* head, int k){
    struct ListNode *node = head, *prev = NULL, *tail = NULL;
    int list_size = 0;
    int head_pos = 0;
    
    /* get list size */
    for (; node; prev = node, node = node->next)
        list_size++;
    if (list_size == 0 || list_size == 1)
        return head;
    
    /* initialize the position and nodes */
    head_pos = list_size - (k % list_size); //FIXME div by 0
    if (head_pos == list_size)
        return head; /* no need to rotate */
    tail = prev;
    node = head;
    prev = NULL;
    
    /* ratate by head_pos */
    for (int i = 0; i < head_pos; i++, prev = node, node = node->next)
        ;
    prev->next = NULL;
    tail->next = head;
    head = node;
    return head;
}

 o -> o -> o -> o -> o -> o -> NULL
head      prev node      tail

114. Flatten Binary Tree to Linked List

문제

주어진 이진 트리를 링크드 리스트로 변환하라. 리스트의 순서는 트리의 preorder 순회 순서이다.

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

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

해결 recursion

구조를 보면 root->right에 gen_list(root->left), 즉 root->left 통째로 리스트로 변환된 헤드를 등록하고. 기존 root->right는 tmp에 저장해두었다가, root->right의 가장 마지막 right에 gen_list(tmp)한것을 등록한다.

주의할 사항은 root->right노드가 위에서 저장했던 tmp노드와 동일하면 바로 gen_list(tmp)해야한다(아래 <- 이 부분).

좋은 문제였다!

struct TreeNode *gen_list(struct TreeNode *root)
{
    if (root == NULL)
        return NULL;
    struct TreeNode *tmp = root->right;
    if (root->left) {
        root->right = gen_list(root->left);
        root->left = NULL;
    }
    if (root->right) {
        struct TreeNode *right_last = root->right;
        if (right_last == tmp) {  		// <- 이 부분
            right_last = gen_list(tmp);
        } else {
            for (; right_last->right != NULL; right_last = right_last->right)
                ;
            right_last->right = gen_list(tmp);
        }
    }
    return root;
}

void flatten(struct TreeNode* root){
    root = gen_list(root);
}

24. Swap Nodes in Pairs

문제

주어진 링크드 리스트에서 한 pair씩 swap해라.

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

https://leetcode.com/problems/swap-nodes-in-pairs/

해결 아이디어 (iterative)

• first, second노드를 지정하고 swap. 이것을 두칸식 반복하는게 기본 아이디어. 어려웠다ㅇㅇ. 비슷하게는 풀다가 답이 안나와서 솔루션 슬쩍 참고함.
• first->next는 second->next를 가리키면 됨. 즉 1번 노드가 3을 가리키면 됨. 굳이 여기서 다음스텝의 swap이후 위치인 4를 가리킬 필요 없음. (나는 이 부분을 틀림)
• 한번에 두개씩 해결해 나가야함. (요게 핵심)
• prev노드는 이전의 first가 되며, 현재의 second를 가리켜야함.
• 생각해보면 그림대로 노드의 링크를 연결하면 되긴함..
• prev는 NULL로 시작했기 때문에 prev가 NULL이면 newhead = second로 초기화.
• 추가로 변수명을 잘 지어야한다는 사실을 또한번 깨달음. 변수명을 잘못지으면 인지부하가 급격히 증가한다. first, second로 지으니 인지부하가 확 줄어드는게 느껴짐.
• Leetcode 해설
  • 1
    
  • 2
    
  • 3
    

해결 iterative

struct ListNode* swapPairs(struct ListNode* head){
    struct ListNode* first = head, *prev = NULL, *second = head, *newhead = head;
    
    while (head && head->next) {
        /* initial first second */
        first = head;
        second = head->next;
        
        /* swap */
        first->next = second->next;
        second->next = first;
        if (prev)
            prev->next = second;
        else
            newhead = second; // set newhead (only one time)
        
        /* set a new head & prev for next step */
        prev = first;
        head = first->next;
    }
    return newhead;
}

해결 recursive

핵 간단하고 천재적인 풀이법. 항상 재귀는 정답을 리턴한다. first->next에는 그다음의 모든 노드들이 정렬을 마친 첫번째 노드를 가리키게하면 된다. first->next 에 swapPairs(second->next)를 저장하고. 재귀적으로 최종 모두정렬된 노드가 리턴된다. 재귀는 참 마법같다..

struct ListNode* swapPairs(struct ListNode* head){
    if (!head || !head->next)
        return head;
    struct ListNode* first = head, *second = head->next;
    
    first->next = swapPairs(second->next);
    second->next = first;
    
    return second;
}

234. Palindrome Linked List

문제

주어진 singlely 링크드 리스트의 노드가 palindrome인지 확인하라.

Input: head = [1,2,2,1]
Output: true

https://leetcode.com/problems/palindrome-linked-list/

해결 O(N) / O(N)

일단 리스트의 배열값을 추가 배열에 저장하고 그 배열값이 palindrome인지 확인. O(N)이긴 한데 더 효율적인 방법이 있을것.
배열을 새로 추가했으니 공간복잡도는 O(N)

int arr[100001];
bool isPalindrome(struct ListNode* head) {
    struct ListNode *node = head;
    memset(arr, 0, 100001);
    int arrcnt = 0;
    
    for (; node != NULL; node = node->next)
        arr[arrcnt++] = node->val;
    for (int i = 0; i < (arrcnt / 2); i++) {
        if (arr[i] != arr[arrcnt - 1 - i])
            return false;
    }
    return true;
}

추가로 palindrome 확인을 위해, 배열값이 양끝부터 가운데로 오면서 같은지 비교하는 방법은 아래방식이 더 읽기 쉬운 코드인것같다.

while (left < right) {
    if (arr[left++] != arr[right++])
        return false;
}

해결 O(N) / O(1)

리스트의 중간노드를 얻어내서 절반을 reverse 시키고 하나씩 비교하는 방법. 추가 배열이 필요없어 공간복잡도는 O(1)이다.

• 중간노드를 구하는 방법은 풀이에서 천재적인 아이디어를 배웠는데, 노드를 순회할때 두칸씩 순회하는 노드를 추가로 두면 2/N번만 순회해서 중간노드를 구할 수 있다.

    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;

• reverse linked list
  지난번에 한번 풀어봤던건데, 다시 풀려니 살짝 오래걸림. 링크드리스트 기초 연산이니, 이 패턴 및 구조를 반복해서 잘 숙지 하자.

struct ListNode *reversed_list(struct ListNode *head)
{
    struct ListNode *node = head;
    struct ListNode *prev = NULL; // reverse하면, 첫번째 노드 next는 NULL을 가리켜야함
    struct ListNode *tmp = head;;
    for (;node != NULL; prev = node, node = tmp) {  // prev, node 한칸씩 우측으로
        tmp = node->next;     // next노드 포인터 미리 저장
        node->next = prev;    // next를 prev노드로 변경
    }
    return prev;  // prev를 리턴
}

• 전체 코드

struct ListNode *get_middle_node(struct ListNode *head)
{
    struct ListNode *slow = head;
    struct ListNode *fast = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

struct ListNode *reversed_list(struct ListNode *head)
{
    // 1 -> 2 -> 3 -> 4
    // 1 <- 2 <- 3 <- 4
    struct ListNode *node = head, *prev = NULL, *tmp = head;;
    for (;node != NULL; prev = node, node = tmp) {
        tmp = node->next;
        node->next = prev;
    }
    return prev;
}

bool isPalindrome(struct ListNode* head) {
    struct ListNode *node = head;
    struct ListNode *first_end = get_middle_node(head);
    struct ListNode *reversed_begin = reversed_list(first_end->next);

    while (reversed_begin != NULL) {
        if (node->val != reversed_begin->val)
            return false;
        node = node->next;
        reversed_begin = reversed_begin->next;
    }
    return true;
}

19. Remove Nth Node From End of List

문제

링크드 리스트의 head노드가 주어진다. 해당 링크드리스트의 뒤에서 n번째 노드를 삭제하라.

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

해결 O(N^2)

노드를 순회하면서 매노드마다 n번 이동해서 node->next가 NULL이면 해당 노드를 제거하면 된다.

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode *node = head, *prev = head, *check = head;
    int node_cnt = 0;
    bool found = false;
    
    for (; node != NULL; prev = node, node = node->next) {
        check = node;
        for (int i = 0; i < n; i++) {
            if (i == n - 1 && check->next == NULL) {
                found = true;
                break;
            }
            check = check->next;
        }
        
        if (found) {
            // remove node
            if (node == head)
                head = node->next;
            else
                prev->next = node->next;
            break;
        }
        
    }
    return head;
}

2. Add Two Numbers

문제

주어진 두 링크드 리스트는 각각 10진수 수를 나타낸다(역방향) 가령 [2,4,3]는 342를 나타냄.
두 값의 합을 리스트로 리턴하라.

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

해결

/*
1. in two linked list [2,4,3], [5,6,4]
out : sum of two list 

2. test plan
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
[4] [6]
[0, 1]

3. data structure / algorithm
DS: linked list
ALGO: 
 - add value (with carry value)
 for() l1 != NULL; l1 = l1->next, l2 = l2->next)
    sum = l1 + l2
    ret = add_list(sum)

*/

struct ListNode* new_node(int val)
{
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    struct ListNode* ret = new_node(0);
     struct ListNode* save_ret = ret;
    int carry = 0;
    
    while (l1 || l2 || carry) {
        int sum = 0;
        if (l1) {
            sum += l1->val;
            l1 = l1->next;
        }
        if (l2) {
            sum += l2->val;
            l2 = l2->next;
        }
        if (carry)
            sum += carry;
        carry = (sum > 9) ? 1: 0;
        ret->next = new_node(sum % 10);
        ret = ret->next;            
    }
    return save_ret->next;
}

해결 220905

나중에 다시 c++ 로 풀어봤는데, 이전에 풀었던 방식과 똑같음.. 오히려 코드 복잡도 측면에서 약간 퇴보. 잘하자.

class Solution {
    ListNode *add_node(int val) {
        ListNode *node = new ListNode;
        node->val = val;
        node->next = NULL;
        return node;
    }
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = add_node(0);
        ListNode *node = head;
        int carry = 0;
        
        while (l1 || l2) {
            int calc = carry;
            if (l1) {
                calc += l1->val;
                l1 = l1->next;
            }
            if (l2) {
                calc += l2->val;
                l2 = l2->next;
            }
            if (calc > 9)
                carry = 1;
            else 
                carry = 0;
            calc = calc % 10;
            
            node->next = add_node(calc);
            node = node->next;
        }
        if (carry == 1)
            node->next = add_node(carry);
        
        return head->next;
    }
};

21. Merge Two Sorted Lists

문제

주어진 두 정렬된 링크드 리스트를 합치기(정렬된 상태로)

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

해결 (recursive) - O(n) / O(n)

"재귀함수는 정답을 리턴한다".
mergeTwoLists() 함수에서 list1이 더 작다면 list1->next에 정렬된 정답(mergeTwoLists(list1->next, list2)의 리턴닶)을 저장하면, list1는 최종적으로 정렬이 모두 마무리된 리스트의 head가 된다.
Base Case 는 list 가 NULL을 만났을때.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    /* Base Case */
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;
  
    /* Recursion */
    if (list1->val < list2->val) {
        list1->next = mergeTwoLists(list1->next, list2);
        return list1;
    } else {
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
}

해결 (iterative) - O(n) / O(1)

l1과 l2포인터를 비교하면서 전진 그리고 prev값을 하나씩 뒤 따르게 만듦. new head를 새로 할당하고 new head -> next를 리턴함.

   p    l1
   1 -> 4 -> 5 
 h  
   1 -> 2 -> 3 -> 6
   l2

재귀와 다르게(콜스택 사용) 추가 메모리를 사용하지 않아서 O(1) 공간복잡도를 갖는다.

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *newhead = new ListNode;
        ListNode *prev = newhead;
        
        while (list1 && list2) {
            if (list1->val <= list2->val) {
                prev->next = list1;
                list1 = list1->next;
            } else {
                prev->next = list2;
                list2 = list2->next;
            }
            prev = prev->next;
        }
        prev->next = (list1 == NULL) ? list2 : list1;
        
        return newhead->next;
    }
};