LeetCode

LeetCode-链表操作注意事项

注意1.

  • 这句话什么意思：

    1
    ListNode* dhead = new ListNode(-1);

    新建一个ListNode型ptr，新建一个ListNode结点，用-1初始化这个结点的val变量，用这个ptr指向这个结点。

  • 这句又是都什么意思

    1
    ListNode* curr = dhead;

    新建一个ListNode型指针curr，这个指针中存储dhead中所存储的结点地址。即这两个指针类型变量所存储内容相同。就是一般赋值操作的意义了。

  • 这句又是什么意思

    1
    ListNode node = head;

    实例化一个ListNode，用head的val和next初始化ListNode的val和next。这个operator=是C++帮我们写好的。

所以为了不用单独处理链表的头结点，通常新建一个d_head：ListNode* d_head = new ListNode(-1);，操作过程中，d_head不应该被移动，最后就可以将他delete掉，就像上述code中的伤处操作。

注意2.删除某一个结点

1
2
3
4
5
ListNode* dNode = curr->next; //新建ptr，指向curr->next
...
...
delete dNode; // 删除指针所指向地址的内容，指针所指向地址不变。
dNode = 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
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>

using namespace std;

struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x):val(x), next(NULL){}
};

// 向链表head的pre_val节点后插入val的结点。
void insertNode(ListNode* head, int val, int pre_val){
    ListNode* d_head = new ListNode(-1);
    d_head->next = head;
    while(d_head->val != pre_val){
        d_head = d_head->next;	// dhead 移动了，所以最后不能删
    }
    ListNode* insertNode = new ListNode(val);
    insertNode->next = d_head->next;
    d_head->next = insertNode;
}

// 从链表head中删除delete_val的结点
ListNode* deleteNode(ListNode* head, int delete_val){
    ListNode* dhead = new ListNode(-1); // 新建结点
    dhead->next = head;

    ListNode* curr = dhead;  //新建ptr，指向head
    while(curr->next){
        if(curr->next->val == delete_val){
            ListNode* dNode = curr->next; //新建ptr，指向curr->next
            curr->next = dNode->next;
            // 删处结点
            delete dNode;
            dNode = nullptr;
        }else
            curr=curr->next;
    }
    ListNode* resHead = dhead->next;  //新建ptr，指向dhead->next
    delete dhead;    // 整个过程dhead没有移动，所以可以delete 
    dhead = nullptr;
    return resHead;
}

// 打印当前链表
void printLinkedList(ListNode* head){	
    ListNode* node = head;
    while(node){
        cout<<node->val<<"->";
        node = node->next;
    }
    cout<<"NULL"<<endl;
    return;
}

int main(int argc, char** argv){
    // create a linkedlist
    int length, nodeVal, headVal;
    cin>>length;
    cin>>headVal;
    int count=length;
    ListNode* head = new ListNode(headVal);
    count--;
    ListNode* dhead = head;
    while(count!=0){
        cin>>nodeVal;
        ListNode* node = new ListNode(nodeVal);
        dhead->next = node;
        dhead = dhead->next;
        count--;
    }
    printLinkedList(head);
    //operations
    int insertVal;
    cin>>insertVal;
    insertNode(head, insertVal, 2);
    printLinkedList(head);
    int dln;
    cin>>dln;
    ListNode* nhead = deleteNode(head, dln);
    printLinkedList(nhead);
    return 0;
}

创建链表，打印链表，销毁链表

作为基本操作，为测试时提供便利。先在ListNode定义中中添加一个构造函数：

1
2
3
4
5
6
7
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

传入一个保存结点值的容器，创建链表：

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* createList(vector<int>& nodeVals){
	if (nodeVals.size()==0) 
        return nullptr;
	vector<ListNode*> nodePtr;
	nodePtr.push_back(new ListNode(nodeVals.back()));
	nodeVals.pop_back();
	while(!nodeVals.empty()){
		nodePtr.push_back(new ListNode(nodeVals.back(), nodePtr.back()));
		nodeVals.pop_back();
	}

	return nodePtr.back();
}

遍历打印链表：

1
2
3
4
5
6
7
void showList(ListNode* head){
	for (ListNode* i = head; i!=NULL; i=i->next){
		cout<<i->val<<"->";
	}
	cout<<"NULL"<<endl;
	return ;
}

销毁链表：

1
2
3
4
5
6
7
8
void destroyList(ListNode* head){
	if (head){
		destroyList(head->next);
		delete head;
        head = nullptr;
	}
	return;
}