DAY3 鏈表part01

今日任務(wù)

● 鏈表理論基礎(chǔ)

● 203.移除鏈表元素

● 707.設(shè)計(jì)鏈表

● 206.反轉(zhuǎn)鏈表

鏈表理論基礎(chǔ)

文章鏈接：https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

1、循環(huán)鏈表用于解決約瑟夫環(huán)的問(wèn)題

2、自定義鏈表結(jié)點(diǎn)的結(jié)構(gòu)體

1 struct LinkNode
2 {
3     int val;
4     LinkNode* next;
5     LinkNode():val(0),next(NULL) {}//初始化函數(shù)1；
6     LinkNode(int x):val(x),next(NULL) {}//初始化函數(shù)2;
7     LinkNode(int x,LinkNode *next):val(0),next(next) {}//初始化函數(shù)3；
8 }//自定義結(jié)構(gòu)體時(shí)自選

LinkNode *head= new Linknode(x);

3、若使用C++默認(rèn)的初始化函數(shù)，則初始化不能賦值

LinkNode *head= new Linknode();//即初始化函數(shù)1

203.移除鏈表元素

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode() : val(0), next(nullptr) {}
 7  *     ListNode(int x) : val(x), next(nullptr) {}
 8  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 9  * };
10  */
11 class Solution {
12 public:
13     ListNode* removeElements(ListNode* head, int val) {
14             ListNode* dummy=new ListNode(0);
15             dummy->next=head;
16             ListNode*p=dummy;
17             while(p->next!=NULL)
18             {
19                 if(p->next->val==val) 
20                 {
21                     ListNode* q=p->next;
22                     p->next=p->next->next;
23                     delete(q);//注意釋放
24                 }
25                 else p=p->next;
26             }
27             head=dummy->next;
28             return head;
29     }
30 };

重點(diǎn)掌握虛擬頭節(jié)點(diǎn)dummy的用法

題目鏈接/文章講解/視頻講解：：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html

707.設(shè)計(jì)鏈表

 1 class MyLinkedList {
 2 public:
 3     struct LinkNode
 4     {
 5         int val;
 6         LinkNode* next;
 7         LinkNode(int x):val(x),next(NULL){};
 8     };
 9     MyLinkedList() {
10         dummy=new LinkNode(0);
11         cnt=0;
12     }//掌握類(lèi)的語(yǔ)法
13     
14     int get(int index) {
15         if(index<0||index>=cnt) return -1;
16         else
17         {
18             LinkNode*p=dummy->next;
19             while(index--)
20             {
21                 p=p->next;
22             }//p定位到下標(biāo)為index的位置
23             return p->val;
24         }
25     }
26     
27     void addAtHead(int val) {
28         LinkNode*newNode=new LinkNode(val);
29         newNode->next=dummy->next;
30         dummy->next=newNode;
31         cnt++;
32     }
33     
34     void addAtTail(int val) {
35         LinkNode*newNode=new LinkNode(val);
36         LinkNode*p=dummy;
37         while(p->next!=NULL) p=p->next;
38         p->next=newNode;
39         cnt++;
40     }
41     
42     void addAtIndex(int index, int val) {
43         if(index<0||index>cnt) return;
44         else if(index==cnt) 
45         {
46             addAtTail(val);
47         }
48         else if(index==0) addAtHead(val);
49         else 
50         {
51             //定位到下標(biāo)為index的結(jié)點(diǎn)前一個(gè)結(jié)點(diǎn)52             LinkNode*p=dummy;
53             while(index--)
54             {
55                 p=p->next;
56             }
57             LinkNode* newNode=new LinkNode(val);
58             newNode->next=p->next;
59             p->next=newNode;
60             cnt++;
61         }
62     }
63     
64     void deleteAtIndex(int index) {
65         if(index<0||index>=cnt) return ;
66         else{
67             LinkNode*p=dummy;
68             while(index--)
69             p=p->next;//p指向下標(biāo)為index的結(jié)點(diǎn)前一個(gè)結(jié)點(diǎn)
70 
71             LinkNode*q=p->next;
72             p->next=p->next->next;
73             delete(q);
74             cnt--;
75         }
76     }
77     private:
78     LinkNode*dummy=new LinkNode(0);
79     int cnt;//定義全局變量
80 };
81 
82 /**
83  * Your MyLinkedList object will be instantiated and called as such:
84  * MyLinkedList* obj = new MyLinkedList();
85  * int param_1 = obj->get(index);
86  * obj->addAtHead(val);
87  * obj->addAtTail(val);
88  * obj->addAtIndex(index,val);
89  * obj->deleteAtIndex(index);
90  */

題目鏈接/文章講解/視頻講解：https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html

206.反轉(zhuǎn)鏈表

思路：

解法一：雙指針?lè)?/h3>

 1 class Solution {
 2 public:
 3     ListNode* reverseList(ListNode* head) {
 4         ListNode* temp; // 保存cur的下一個(gè)節(jié)點(diǎn)
 5         ListNode* cur = head;
 6         ListNode* pre = NULL;
 7         while(cur) {
 8             temp = cur->next;  // 保存一下 cur的下一個(gè)節(jié)點(diǎn)，因?yàn)榻酉聛?lái)要改變cur->next
 9             cur->next = pre; // 翻轉(zhuǎn)操作
10             // 更新pre 和 cur指針
11             pre = cur;
12             cur = temp;
13         }
14         return pre;
15     }
16 };

解法二：遞歸還是一如既往的難以理解

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode() : val(0), next(nullptr) {}
 7  *     ListNode(int x) : val(x), next(nullptr) {}
 8  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 9  * };
10  */
11 class Solution {
12 public:
13     ListNode* reverse(ListNode* pre,ListNode*cur) {
14       if(cur==NULL) return pre;
15       ListNode*p=cur->next;
16       cur->next=pre;
17       return reverse(cur,p);
18     }//遞歸函數(shù)，注意返回值
19 
20     ListNode* reverseList(ListNode*head)
21     {
22         return reverse(NULL,head);
23     }//調(diào)用遞歸的函數(shù)
24 };

題目鏈接/文章講解/視頻講解：https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html

總結(jié)：

鏈表的定義；鏈表的基本操作；鏈表反轉(zhuǎn)的兩種方法

posted @ 2024-07-19 16:34 xzdmzrc 閱讀(29) 評(píng)論(0) 收藏舉報(bào)

刷新頁(yè)面返回頂部

xzdmzrc221202