代码随想录 | Day05 | 链表：移除链表元素&&设计链表&&反转链表

主要学习内容：

1.链表删除操作

2.设计自己的链表

3.双指针操作链表

203.移除链表元素

203. 移除链表元素 - 力扣（LeetCode）

解法1：设置虚拟头结点

设置一个虚拟头结点用虚拟头结点的next进行判断

好处是不需要写关于头结点的处理逻辑，比较容易处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode * t=new ListNode;
        ListNode * q=new ListNode;
        t->next=head;
        q=t;
        while(t->next!=NULL)
        {
            if(t->next->val==val)
            {
                ListNode *tmp=t->next;
                t->next=t->next->next;
                delete tmp;
            }
            else
                t=t->next;
        }
        return q->next;
    }
};
关键点：

1.设置一个额外的指针q指向虚拟头结点，head节点可能会被删除，最后无法返回结果

2.手动释放内存 delete

解法2：直接删除

思路：先处理头节点再处理其余节点

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
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while(head && head->val==val)
        {
            ListNode * tmp= head;
            head=head->next;
            delete tmp;
        }
        ListNode * t=new ListNode;
        t=head;
        while(t && t->next!=NULL)
        {
            if(t->next->val==val)
            {
                ListNode *tmp=t->next;
                t->next=t->next->next;
                delete tmp;
            }
            else
                t=t->next;
        }
        return head;
    }
};

关键点：

1.头结点是val头结点连着的下面几个可能也是val，所以要用while而不是if来处理头结点

2.没有了虚拟头结点，我们就不知道第一个到底是不是为空，则需要在两个while（）处加入head不为空的判断条件

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
class MyLinkedList {
public:
    struct ListNode
     {
     int val;
     ListNode *next;
     ListNode *pre;
     ListNode() : val(0), next(nullptr),pre(nullptr) {}
 };

    MyLinkedList() {
        prenode=new ListNode;
        _size=0;
    }
    
    int get(int index) {

        if(index>(_size-1)||index<0)
            return -1;

        int n=index+1;
        ListNode *p=new ListNode;
        p=prenode;
        while(n--&&p->next!=NULL)
            p=p->next;
        return p->val;
        
    }
    
    void addAtHead(int val) {
        ListNode* p=new ListNode;
        p->next=prenode->next;
        prenode->next=p;
        if(p->next!=nullptr)
            p->next->pre=p;
        p->val=val;
        p->pre=prenode;
        _size++;
    }
    
    void addAtTail(int val) {
        ListNode* p=new ListNode;
        p->next=NULL;
        p->val=val;
        ListNode* q=new ListNode;
        q=prenode;
        while(q->next!=NULL)
            q=q->next;
        q->next=p;
        p->pre=q;
        _size++;
    }   
    
    void addAtIndex(int index, int val) {
        if(index<0)
        {
            addAtHead(val);
        }
           
        if(index>_size)
            return ;
        else if(index==_size)
        {
            addAtTail(val);
        }
        else
        {
            int n=index;
            ListNode *p=new ListNode;
            p=prenode;
            ListNode *q=new ListNode;
            while(n--&&p->next!=NULL)
                p=p->next;
            q->next=p->next;
            p->next=q;
            q->val=val;
            _size++;
        }
    }
    
    void deleteAtIndex(int index) {
        if(_size==0)
            return;
        if(index>=_size||index<0)
            return ;
        int n=index;
        ListNode *p=new ListNode;
        p=prenode;
        while(n--&&p->next!=NULL)
            p=p->next;
        if(p->next==nullptr)
            return;
        ListNode *q=p->next;
        p->next=q->next;
        if (q->next != NULL)
        {
            q->next->pre = p;//更新前后节点的连接
        }
        _size--;
    }
private:
    ListNode *prenode;
    int _size;
};

707.设计链表

707. 设计链表 - 力扣（LeetCode）

解法一：单链表

注意的点：

addAtIndex函数的if条件里面是要index>size而不是index>=size，因为=的时候是要插入到末尾

（改了2小时才发现，无语住了╭(╯^╰)╮）

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
class MyLinkedList {
public:
    struct ListNode
    {
        struct ListNode* next;
        int val;
        ListNode() {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode* next) : val(x), next(next) {}
    };

    MyLinkedList()
    {
        size = 0;
        prenode = new ListNode;
    }

    int get(int index)
    {
        if (index < 0 || index >= size)
            return -1;
        ListNode* t = new ListNode;
        t = prenode;
        int n = index + 1;
        while (n--)
        {
            t = t->next;
        }
        return t->val;
    }

    void addAtHead(int val)
    {
        ListNode* t = new ListNode;
        t->val = val;
        t->next = prenode->next;
        prenode->next = t;
        size++;
    }

    void addAtTail(int val)
    {
        ListNode* t = prenode;
        int n = size;
        while (n--&& t->next != NULL)
            t = t->next;

        ListNode* tmp = new ListNode;
        tmp->val = val;
        tmp->next = NULL;
        t->next = tmp;
        size++;
    }

    void addAtIndex(int index, int val)
    {
        if (index < 0 || index > size)
            return;
        ListNode* t = prenode;
        if (index == 0)
            addAtHead(val);
        else
        {
            while (index--)
                t = t->next;
            ListNode* q = new ListNode;
            q->val = val;
            q->next = t->next;
            t->next = q;
            size++;
        }
    }

    void deleteAtIndex(int index)
    {
        if (size == 0)
            return;
        if (index < 0 || index >= size)
            return;
        if (index == 0)
        {
            ListNode* t = new ListNode;
            t = prenode->next;
            prenode->next = prenode->next->next;
            size--;
            delete t;
        }
        else
        {
            ListNode* t = prenode;
            while (index-- && t->next)
                t = t->next;
            ListNode* p = new ListNode;
            p = t->next;
            t->next = t->next->next;
            delete p;
            size--;
        }
    }

private:
    ListNode* prenode;
    int size;
    
};

解法二：双链表

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
class MyLinkedList {
public:
    struct ListNode
     {
     int val;
     ListNode *next;
     ListNode *pre;
     ListNode() : val(0), next(nullptr),pre(nullptr) {}
 };

    MyLinkedList() {
        prenode=new ListNode;
        _size=0;
    }
    
    int get(int index) {

        if(index>(_size-1)||index<0)
            return -1;

        int n=index+1;
        ListNode *p=new ListNode;
        p=prenode;
        while(n--&&p->next!=NULL)
            p=p->next;
        return p->val;
        
    }
    
    void addAtHead(int val) {
        ListNode* p=new ListNode;
        p->next=prenode->next;
        prenode->next=p;
        if(p->next!=nullptr)
            p->next->pre=p;
        p->val=val;
        p->pre=prenode;
        _size++;
    }
    
    void addAtTail(int val) {
        ListNode* p=new ListNode;
        p->next=NULL;
        p->val=val;
        ListNode* q=new ListNode;
        q=prenode;
        while(q->next!=NULL)
            q=q->next;
        q->next=p;
        p->pre=q;
        _size++;
    }   
    
    void addAtIndex(int index, int val) {
        if(index<0)
        {
            addAtHead(val);
        }
           
        if(index>_size)
            return ;
        else if(index==_size)
        {
            addAtTail(val);
        }
        else
        {
            int n=index;
            ListNode *p=new ListNode;
            p=prenode;
            ListNode *q=new ListNode;
            while(n--&&p->next!=NULL)
                p=p->next;
            q->next=p->next;
            p->next=q;
            q->val=val;
            _size++;
        }
    }
    
    void deleteAtIndex(int index) {
        if(_size==0)
            return;
        if(index>=_size||index<0)
            return ;
        int n=index;
        ListNode *p=new ListNode;
        p=prenode;
        while(n--&&p->next!=NULL)
            p=p->next;
        if(p->next==nullptr)
            return;
        ListNode *q=p->next;
        p->next=q->next;
        if (q->next != NULL)
        {
            q->next->pre = p;//更新前后节点的连接
        }
        _size--;
    }
private:
    ListNode *prenode;
    int _size;
};
关键点：

1.记得释放空间

2.很需要虚拟头指针和size，可以对很多操作进行简化

206.反转链表

206. 反转链表 - 力扣（LeetCode）

解法1：双指针

快慢指针分别指向需要改变指向的两个结点，然后进行翻转即可

206.翻转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//自己写的
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        if(head==NULL)
            return head;
        ListNode * pre=NULL;//慢指针
        ListNode * cur=head;//快指针
        ListNode * tmp=head->next;//保存节点所用
        while(cur)
        {
            cur->next=pre;//翻转操作
            //快慢指针更新
            pre=cur;
            cur=tmp;
            if(tmp)
                tmp=tmp->next;//更新保存点
        }
        return pre;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//代码随想录的
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->next，改变后依靠这个才能找到下一结点
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针，pre和cur前移
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

改进：

用tmp=cur->next来更新tmp，使得cur和tmp产生关联，和循环条件统一起来，当tmp=NULL时，不会因为使用tmp->next而报错。

解法2：递归法

递归由方法一改写而来

递归结束条件对应while循环结束条件

快慢指针前移过程由向下一个递归函数进行赋值来代替，下一次的pre和cur（即需要翻转的两个结点）作为形参传入

最后返回的就是pre

（如果不太明白的小伙伴可以暂时放一放，可以等做完回溯章节再回来，会好很多很多很多很多）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    ListNode* re(ListNode *cur,ListNode * pre)
    {
        if(cur==NULL)//递归结束条件对应while循环条件
            return pre;//返回头结点
        ListNode * tmp=cur->next;//保存cur的下一结点
        cur->next=pre;//翻转操作
        //递归的过程就是快慢指针前移的过程
        //pre=cur;
        //cur=tmp;
        return re(tmp,cur);
    }
    ListNode* reverseList(ListNode* head) 
    {
        return re(head,NULL);
    }
};