第二讲 线性表

1. 将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。

2. 对于线性表中的数据来说，位于当前数据之前的数据统称为“前趋元素”，前边紧挨着的数据称为“直接前趋”；同样，后边的数据统称为“后继元素”，后边紧挨着的数据称为“直接后继”。

3. 线性表的分类

(1) 数据元素在内存中集中存储，采用顺序表示结构，简称“顺序存储”；
例如：数组
(2) 数据元素在内存中分散存储，采用链式表示结构，简称“链式存储”。
例如：单链表、双链表、循环单（双）链表

4. 不同实现方式的时间复杂度（不要硬背结论、要从实现方式入手分情况讨论，下述为特定情况下的时间复杂度）

(1) 数组：随机索引O(1)、插入O(n)、删除O(n)
(2) 单链表：查找某一元素O(n)、插入O(1)、删除O(n)
(3) 双链表：查找某一元素O(n)、插入O(1)、删除O(1)

5. 考题：、2016-2、2012-42、2015-41、2019-41

2016-1

image-20210703145004164

c a e b d NULL

​ f

image-20210703211438769

2016-2

image-20210703145156452

image-20210703211623904

image-20210705123934999

2012-42

image-20210703205443192

image-20210703213333780

acwing 66 两个链表的第一个公共结点

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
   ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
       auto p = headA;
       auto q = headB;
       while(p!=q){
           if(p)
           p = p->next;
           else p = headB;
           if(q)
           q = q->next;
           else q = headA;
       }
       return p;
   }
};

c:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
>/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/
>struct ListNode *findFirstCommonNode(struct ListNode *headA, struct ListNode *headB) {
   
   struct ListNode *p = headA;
   struct ListNode *q = headB;
   
   while(p!=q){
       
       if(p){
           p= p->next;
           
       }else p = headB;
       
        if(q){
           q= q->next;
           
       }else q = headA;
       
   }
   
   return p;
   
>}

image-20210703210247841

2015-41

image-20210703205625516

删除节点

image-20210704125135359

acwing 3756. 筛选链表

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
>/**
>* Definition for singly-linked list.
>* struct ListNode {
>*     int val;
>*     ListNode *next;
>*     ListNode(int x) : val(x), next(NULL) {}
>* };
>*/
>class Solution {
>public:
  ListNode* filterList(ListNode* head) {
      bool stu[10000+5]={false};
      stu[abs(head->val)] = true;
      for(auto p = head; p->next ;){

          auto t = abs(p->next->val);
          if(stu[t]){
              // 已经存在，删除
              auto q  = p->next;
              p->next = q->next;
              delete q;


          }else{
              // 不存在，
              stu[t] = true;
              p = p->next;


          }

      }

      return head;
  }
>};

c:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
>/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
* 
* Note: The returned array must be malloced, assume caller calls free().
*/
>struct ListNode* filterList(struct ListNode* head) {
   
   bool stu[10000+5] = {false};  //记录节点中的值是否被使用了
   
   stu[abs(head->val)] = true;   // 第一个节点的值使用后  
   
   for(struct ListNode *p = head ; p->next ;){
       
       int x = abs( p->next->val );
       
       if(stu[ x ] ) // 判断此时节点的值是否被使用
       {
           // 已经存在，使用过 删除值一样的结点
           struct ListNode *q = p->next;
           p->next = q->next;
           free(q);
           
       }else{
           // 此时节点的值第一次出现，现在标记使用
           stu[x] = true;
           p=p->next ; // 到下一个结点；
           
           
       }
       
       
   }
   
   return head;
>}

image-20210703210639180

image-20210703210730300

2019-41

image-20210703205709442

image-20210703205858599

image-20210703214728201

image-20210703215430852

image-20210703215419546

image-20210703220727048

q

acwing 3757. 重排链表

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void rearrangedList(ListNode* head) {
        // 如果链表只有一个元素 , 不用处理直接打印
       if(head->next == NULL) return ; 
        
        // 链表长度
        
        int n = 0;
        
        for(auto t = head;t;t =t->next){
            // cout<<head->val;
            n++;
        }
      
        // cout<<n<<endl;
        
        // 前半段的结点数， 链表分为2段 1~mid-1 , mid ~ n;
        int mid  = (n+1)/2;
        auto a  = head;
        for(int i=0;i<mid-1;i++)a=a->next;
        
        auto b =a->next;
        auto c = b ->next;
        
        a->next = NULL;
        b->next = NULL;
        
        // 翻转 mid ~ n  到n~mid;
        while(c){
            
            // 预存后面的节点地址
            auto t  = c->next;
            c->next = b; // 翻转
            
            //b,c 后移一位
            b = c;
            c = t;
            
        }
        // 1~mid-1与 n ~ mid 合并      b此时已经到最后一个节点，c是NULL
        
        for(auto p = head, q= b; q; ){
            
            // 预存q->next 的节点
            auto t = q->next ;
            
            //p与q连接
            q->next = p->next;
            p->next = q;
            
            
            // p,q 后移
            p = q->next; // or p=p->next->next  此时这里 p->next就是q
            q= t  ;  // q 到之前预存的t的位置
            
            //循环实现，达到合并
        }
        
       
        return;
    }
};

c:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void rearrangedList(struct ListNode* head) {
    
      // 如果链表只有一个元素 , 不用处理直接打印
       if(head->next == NULL) return ; 
        
        // 链表长度
        
        int n = 0;
        
        for(struct ListNode* t = head;t;t =t->next){
            // cout<<head->val;
            n++;
        }
      
        // cout<<n<<endl;
        
        // 前半段的结点数， 链表分为2段 1~mid-1 , mid ~ n;
        int mid  = (n+1)/2;
        struct ListNode* a  = head;
        for(int i=0;i<mid-1;i++)a=a->next;
        
        struct ListNode* b =a->next;
        struct ListNode* c = b ->next;
        
        a->next = NULL;
        b->next = NULL;
        
        // 翻转 mid ~ n  到n~mid;
        while(c){
            
            // 预存后面的节点地址
            struct ListNode* t  = c->next;
            c->next = b; // 翻转
            
            //b,c 后移一位
            b = c;
            c = t;
            
        }
        // 1~mid-1与 n ~ mid 合并      b此时已经到最后一个节点，c是NULL
        struct ListNode* q= b;
        for(struct ListNode* p = head; q; ){
            
            // 预存q->next 的节点
            struct ListNode* t = q->next ;
            
            //p与q连接
            q->next = p->next;
            p->next = q;
            
            
            // p,q 后移
            p = q->next; // or p=p->next->next  此时这里 p->next就是q
            q= t  ;  // q 到之前预存的t的位置
            
            //循环实现，达到合并
        }
        
       
        return;
    
    
}

image-20210703210845455

image-20210703210917316

6. 押题：AcWing 34、AcWing 1451

AcWing 34

AcWing 1451