刷題 - 資料結構（二）連結清單

1. 連結清單

1.1 題目：合并兩個有序連結清單

連結清單的建立與插入：關鍵在于留出頭部，建立疊代指針。

ListNode* head = new ListNode; // 通過new 建立了一個資料類型為ListNode的資料 并把該資料的位址指派給ListNode
    ListNode* p = 0; // 再建立一個資料類型為ListNode的資料 并把該資料的位址指派給ListNode
    p = head; // 把head 裡面的位址指派給p

完整的代碼

作者：小陳寫不完代碼
連結：https://zhuanlan.zhihu.com/p/365219765
來源：知乎
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

#include<iostream>
#include<string>
using namespace std;
struct node
{
    string name;
    int score;
    node* next;
};
node* creatList(); // 建立了一個傳回值為指向資料類型為node的執政,即傳回的是一個位址
int main()
{
    node* head=creatList();
}
node* creatList()
{
    node* head = new node; // 通過new 建立了一個資料類型為node的資料 并把該資料的位址指派給node
    node* p= new node; // 再建立一個資料類型為node的資料 并把該資料的位址指派給node
    p=head; // 把head 裡面的位址指派給p
    p->next=NULL; //這裡把p指向的資料類型為node的資料裡的 指針next指向了空.指針必須有對象 即指向一個地方,你不告訴它 它就亂跑 是以一般都是讓它空着
    while (true) // 這裡我選擇while循環 因為裡面是true 是以會一直進行 ,我們在裡面使用條件判斷加break跳出來
    {
        cout<<"Please enter student name: ";
        cin>>p->name; // 錄入學生的姓名
        cout<<"Please enter student score: ";
        cin>>p->score; // 輸入學生的分數
        if(p->score <0){
            break; // 如果分數小于0 跳出循環即輸入結束.
        }
        node*q =new node; // 沒有跳出循環 即繼續輸入,這時我們再建立一個這些資料類型為node的資料 并把它的位址指派給 指針變量 q .
        p->next=q; // 剛剛p指針指向的資料類型為node的資料裡的 指針next 指向 q ,節點p 和 節點q連起來了..
        q->next=NULL; // 指針q指向的資料類型為node的資料裡的指針 next 指針也不能亂指,是以我們讓它指向 NULL
        p=q; // 這裡我當初就搞了很長時間.還記的嘛 p 和 q 是什麼 ,它們兩都是指針變量.它們裡面放的是位址,而且它們裡面的位址是可以給其它的指向相同資料類型的指針的,這裡我們把q裡面的位址 給了p 這樣p裡面存放的位址就是這個連結清單的最後一個節點的位址.如此反複我們就實作了動态輸入.
    }
    return head; // 這就是為什麼我們要設定head了,因為p的位址是不斷變化的,而head裡面的位址是不變的.而且head裡面放的就是第一個節點的位址,
}

或者

// 連結清單的建立
#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;
struct ListNode
{
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {};
};
void addToTail(ListNode** head, int val)
{
    ListNode* node = new ListNode(val);
    if (!*head)
    {
        *head = node;
    }
    else
    {
        ListNode* tmp = *head;
        while (tmp->next)
            tmp = tmp->next;
        tmp->next = node;
    }

}

void printList(ListNode* head)
{
    ListNode* tmp;
    tmp = head;
    if (tmp == NULL)
        cout << "empty list";
    else
    {
        while (tmp != NULL)
        {
            cout << tmp->val << ',';
            tmp = tmp->next;
        }
        cout << endl;
    }

}

 
int main()
{
    int lt = time(NULL);
    srand(lt);
    int len = 1;
    int a[] = { 1,2,4 };
    int a2[] = { 1,3,4 };
    ListNode* root2 = NULL;

    ListNode* root1 = NULL;  ListNode* root3 = 0;
    for (auto i:a)
        addToTail(&root1,i);
    for (auto i : a2)
        addToTail(&root2, i);
 
}

依據數組建立清單的時候，需要考慮到：函數内部不好獲得數組的長度。sizeof 的方法解除安裝main中可以，但是對于函數的形參指針就不行了。

解決方法：類模闆+引用。

template<class T>
void arr(T &a)
{
	int n = sizeof(a) / sizeof(a[0]);
	cout << n << endl;
}
 
int main()
{
	int a[] = { 6,-1,3,-4,-6,9,2,-2,5 };
	arr(a);
}

總結：其實就是：确定指向（pre->next = ）,激活目前（pre = pre->next）
總代碼：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);    記錄一下頭的位置
        ListNode* cur = dummy;                            弄個哨兵變量用于周遊
        while (l1 != nullptr && l2 != nullptr) {
            ListNode** pp = (l1->val < l2->val) ? &l1 : &l2;
            cur->next = *pp;
            cur = cur->next;
            *pp = (*pp)->next;
        }
        cur->next = (l1 == nullptr) ? l2 : l1;

        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }

2023年2月23日更新這個題目

今天又遇到。

能否在節點調節指針走向？

應該不行。分析後發現，這個思路依據 “目前指向next < 對面的值”，你這個對面的值怎麼表達？
為什麼要用指針的指針？

是這樣的，你一會要更新l1, 一會是 l2，這就需要用到指針的指針。

下面是我的代碼，犯了幾個錯誤。

1 . 關心下一個而不是本體導緻了循環的思路不清晰；

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* temp1 = list1;
    ListNode* temp2 = list2;
    ListNode* dummy = new ListNode(0);
    ListNode* cur = dummy;
    if (list2->val <= list1->val)
    {
        dummy->next = list2;
        cur = list2;
    }
    else
    {
        dummy->next = list1;
        cur = list1;
    }
    while((list1)&& (list2))
    { 
        if (cur->next->val <= list1->next->val)
        {
            temp2 = temp2->next;
            list2->next = list1;     
            list2 = temp2;
        }
        else
        {
            temp1 = temp1->next;
            list1->next = list2;
            list1 = temp1;
        }
    }
    return dummy->next;
}

修改後

ListNode* mergeTwoLists(ListNode * l1, ListNode * l2) {
    ListNode* dummy = new ListNode(0);    //記錄一下頭的位置
        ListNode* cur = dummy;
        while (l1 != nullptr && l2 != nullptr)
        {       
            if (l1->val < l2->val)
            {
                cur->next = l1;
                cur = cur->next;
                l1 = l1->next;
            }
            else
            {
                cur->next = l2;
                cur = cur->next;
                l2 = l2->next;
            }
}
    cur->next = (l1 == nullptr) ? l2 : l1;
    ListNode* ans = dummy->next;
    delete dummy;
    return ans;
}

2. 删除排序連結清單中的重複元素

// 原來的代碼有錯誤
ListNode* deleteDuplicates(ListNode* head) {   
    ListNode* new_head = new ListNode(head->val);
    ListNode* h = new_head;
    int temp = head->val;
    head = head->next;
    while (head != nullptr) {
        if (head->val != temp) {
            h->next = head;
            h = h->next;
        }


        temp = head->val;
        head = head->next;
    }
    return new_head;
}

修改了

ListNode* deleteDuplicates(ListNode* head) {
           if (!head) {
            return head;
        }
    ListNode* new_head = new ListNode(head->val);
    ListNode* h = new_head;
    int temp = head->val;
    head = head->next;
    while (head != nullptr) {
        if (head->val != temp) {
            h->next = head;
            h = h->next;
            temp = head->val;
            head = head->next;
        }
        else {
            temp = head->val;
            head = head->next;
            h->next = head; // 這句話一定要，他不是定義，他是修改！！！
        }
        
    }
    return new_head;
}

題目四、删除連結清單的倒數第 N 個結點

開始的想法：

必須獲得連結清單長度；（後面發現不一定）
循環到某個的時候跳過就好

但是發現還少了一些
必須要用啞結點（頭節點要一視同仁）；

下面是我的代碼，沒用到啞結點，要不斷排除特殊情況。

ListNode* removeNthFromEnd(ListNode* head, int n) {
    int n1 = 0;
    ListNode* cur = head;
    while (cur != nullptr) {
        ++n1;
        cur = cur->next;
    }
    if (n1 ==1) return head->next;  // 啰嗦了，但是必要的
    int k = 0;
    cur = head;
    if (k > n1 - n -1) return head->next;
    while (k < n1 - n -1) {
        ++k;
        cur = cur->next;
    }
    cur->next = cur->next->next;
    return head;
    }

把上面的代碼稍微修改，加入啞結點就好。

class Solution {
public:
    int getLength(ListNode* head) {
        int length = 0;
        while (head) {
            ++length;
            head = head->next;
        }
        return length;
    }

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode* cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur->next;
        }
        cur->next = cur->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

作者：LeetCode-Solution
連結：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

當然，雙指針發可以避免擷取總長度

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* first = head;
        ListNode* second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first->next;
        }
        while (first) {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

作者：LeetCode-Solution
連結：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-b-61/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

刷題 - 資料結構（二）連結清單

1. 連結清單

1.1 題目：合并兩個有序連結清單

2023年2月23日更新這個題目

2. 删除排序連結清單中的重複元素

題目四、删除連結清單的倒數第 N 個結點

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

刷題 - 資料結構（二）連結清單

1. 連結清單

1.1 題目：合并兩個有序連結清單

2023年2月23日 更新這個題目

2. 删除排序連結清單中的重複元素

題目四、 删除連結清單的倒數第 N 個結點

繼續閱讀

2023年2月23日更新這個題目

題目四、删除連結清單的倒數第 N 個結點