Linked list

Linked List in C++ STL

int main()
{
    list<int> data;
    int value;
    do{
      cout<<"Enter a number:";
      cin>>value;
      if(value){
        data.push_front(value);
      }
    }while(value);
for(auto iter=data.begin();iter != data.end();iter++){
        cout<<*iter<<" ";
    }
    return 0;
}

LeetCode #83. Remove Duplicates from Sorted List

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Example 1

Example 2

解題邏輯：
head不動，利用一個cur指標來處理遍尋及刪除的動作。
1.判斷如果為空list，或是只有一個node：直接回傳head指到的內容。
2.當目前的node及下一個node均非null
判斷目前node的val跟下一個node的val 是否相同。
1) 相同：
1–1. 用tmp指到下下一個node。
1-2. 刪除目前指到的下一個node。
1–3. 將目前node指到tmp。
2)不同：指標向下一個node移動。

/**
 * 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* deleteDuplicates(ListNode* head) {
        if(head == nullptr || head->next == nullptr)
            return head;
        
        ListNode* current = head;
        ListNode* tmp;
        
        while(current && current->next){
            if(current->val == current->next->val){
                tmp = current-> next -> next;
                delete current -> next;
                current -> next = tmp;
            }else{
                current = current ->next;
            }
}
        return head;
    }
};

LeetCode #21. Merge Two Sorted Lists

題目：
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.

Example

解題邏輯：
建立一個空的節點，因為節點才有next可以使用，並將head指向它，
最後要回傳的是head -> next。
head跟cur都指向空節點，
開始逐一比較list1跟list2每一個節點大小，並將cur->next指向當前有較小val的節點，

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
  /*開出一個空節點，必須讓head指向一個節點
  因為節點裡面才有next指標
  最後這個空節點不需要輸出
  */
        ListNode* head = new ListNode(0);
        ListNode* current = head;
        
        while(list1 && list2){
        //list1 跟list2都還沒走完
            if(list1 -> val > list2 -> val){
            //list1目前的節點值較大，return list連到較小的list
                current -> next = list2;
                list2 = list2 ->next;
            }else{
                current -> next = list1;
                list1 = list1 -> next;
            }
            //每走完一輪current要往後移動
            current = current -> next;
        }
        
        //處理一個list走完，另一個還沒走完的情況。
        if(list1){
            current ->next = list1; 
        }else if(list2){
            current -> next = list2;
        }
        //回傳head的下一個
        return head->next;
    }
};

LeetCode #24. Swap Nodes in Pairs (medium)

題目：
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

正常的list情境

null list及single node

解題思維：這題可以使用遞迴的方式，

Return the head of the merged linked list.