链表

一、定义与方法

使用结构体

1
2
3
4
5
6
// 单链表
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x): val(x), next(NULL) {}  // 节点的构造函数
};

使用类

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
class LNode {
public:
    int val;
    LNode *next;

    LNode(int x) : val(x), next(nullptr) {}
};

class LinkedList {
private:
    LNode *head;
public:
    LinkedList() : head(nullptr) {}
    
    void append(int data) {
        LNode *newNode = new LNode(data);
        if (head == nullptr){
            LNode* dummyHead = new LNode(0);
            head=dummyHead;
            head->next= newNode;
        } 
        else{
            LNode *cur = head;
            while (cur->next!= nullptr)
                cur=cur->next;
            cur->next = newNode;
        }
    }
    
    void printList(){
        LNode *cur = head->next;
        while(cur!=nullptr){
            std::cout << cur->val;
            cur=cur->next;
            if(cur==nullptr) std::cout<< std::endl;
            else cout <<" ";
        }
    }

    int len(){
        LNode *cur = head->next;
        int n=0;
        while(cur!=nullptr){
            cur=cur->next;
            n++;
        }
        return n;
    }
    
    void insert(int pos,int data){
        if(pos>len()||pos<1)
            cout<<"Insertion position is invalid."<<endl;
        else{
            LNode *newNode = new LNode(data);
            LNode *cur = head,*pre;
            while(pos--){
                pre = cur;
                cur = cur->next;
            }
            newNode->next=cur;
            pre->next = newNode;
            printList();   
        }
    }
    void deleteL(int pos){
        if(pos<1||pos>len())
            cout<<"Deletion position is invalid."<<endl;
        else{
            LNode *cur = head,*pre;
            while(pos--){
                pre=cur;
                cur=cur->next;
            }
            pre->next = cur->next;
            printList();
        }
    }
};

二、相关题目

203.移除链表元素

题目链接

注意：
1.使用虚拟头节点方便操作
2.注意移除节点后删除内存（包括虚拟头节点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *dummyhead = new ListNode(0);
        dummyhead->next = head;
        ListNode *cur = dummyhead;
        while(cur->next!=nullptr){
            if(cur->next->val==val){
                ListNode *tem = cur->next;
                cur->next=tem->next;
                delete tem;
            }else cur=cur->next;
        }
        head=dummyhead->next;
        delete dummyhead;
        return head;
    }
};

707.设计链表

题目链接

类的初始化中，使用私有变量来记录长度和虚拟节点

1
2
3
4
private:
    int _size;
    LinkedNode * _dummyhead;
};

1
2
3
4
MyLinkedList() {
        _size = 0;
        _dummyhead = new LinkedNode(0);
    }

删除节点后将tmp指向nullptr
1
2
3
4
5
6
delete tmp;
      //delete命令指示释放了tmp指针原本所指的那部分内存，
      //被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，
      //如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
      //如果之后的程序不小心使用了tmp，会指向难以预想的内存空间
      tmp=nullptr;

完整代码

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
class MyLinkedList {

public:
    // 定义链表节点结构体
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };

    MyLinkedList() {
        _size = 0;
        _dummyhead = new LinkedNode(0);
    }
    
    int get(int index) {
        if(index>(_size-1)||index<0) return -1;
        LinkedNode *cur=_dummyhead->next;
        while(index--)
        {
            cur=cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        LinkedNode *newLNode = new LinkedNode(val);
        newLNode->next = _dummyhead->next;
        _dummyhead->next = newLNode;
        _size++;
    }
    
    void addAtTail(int val) {
        LinkedNode *newLNode = new LinkedNode(val);
        LinkedNode *cur=_dummyhead;
        while(cur->next!=nullptr){
            cur=cur->next;
        }
        newLNode->next = cur->next;
        cur->next = newLNode;
        _size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index>_size||index<0)return;
        LinkedNode *newLNode = new LinkedNode(val);
        LinkedNode *pre=_dummyhead;
        while(index--){
            pre=pre->next;
        }
        newLNode->next = pre->next;
        pre->next = newLNode;
        _size++;

    }
    
    void deleteAtIndex(int index) {
        if(index<0||index>(_size-1)) return;
        LinkedNode *pre=_dummyhead,*tem;
        while(index--){
            pre=pre->next;
        }
        tem=pre->next;
        pre->next=tem->next;
        delete tem;
        _size--;

    }
private:
    int _size;
    LinkedNode * _dummyhead;
};

206.反转链表

题目链接
第一版

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* reverseList(ListNode* head) {
        // 原地逆置
        if (head == nullptr)
            return head;
        else {
            ListNode* dummyNode = new ListNode(0);
            ListNode *cur = head, *nex;
            while (cur!= nullptr) {
                nex = cur->next;
                cur->next = dummyNode->next;
                dummyNode->next = cur;
                if(nex==nullptr)break;
                else{
                    cur = nex;
                    nex = nex->next;
                }
            }
            cur = dummyNode->next;
            delete dummyNode;
            return cur;
        }
    }
};

缺点: 虚拟头节点

改进方法1: 双链表法
时间复杂度 : $O(n)$
空间复杂度 : $O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
            cur = temp;
        }
        return pre;
    }
};

其余方法：递归法
时间复杂度 : $O(n)$
空间复杂度 : $O(n)$

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
class Solution {
public:
	//方法1
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        // 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
        // pre = cur;
        // cur = temp;
        return reverse(cur,temp);
    }
    ListNode* reverseList1(ListNode* head) {
        // 和双指针法初始化是一样的逻辑
        // ListNode* cur = head;
        // ListNode* pre = NULL;
        return reverse(NULL, head);
    }
    //方法2
	ListNode* reverseList2(ListNode* head) {
        // 边缘条件判断
        if(head == NULL) return NULL;
        if (head->next == NULL) return head;
        
        // 递归调用，翻转第二个节点开始往后的链表
        ListNode *last = reverseList(head->next);
        // 翻转头节点与第二个节点的指向
        head->next->next = head;
        // 此时的 head 节点为尾节点，next 需要指向 NULL
        head->next = NULL;
        return last;
    }

};