Cybay
0%

链表

发表于 更新于 分类于 Valine：
链表

虚拟头节点

移除链表元素

leetcode203https://leetcode.com/problems/r…

1
2
3
4
5
6
7
8
9
//Definition for singly-linked list.
  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
14
15
16
17
18
 // 删除头结点 
        while (head != NULL && head->val == val) { // 注意使用while
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
        }

// 删除非头结点
        ListNode* cur = head;
        while (cur != NULL && cur->next!= NULL) {
            if (cur->next->val == val) {
                ListNode* tmp = cur->next;
                cur->next = cur->next->next;
                delete tmp;
            }
            else 
                cur = cur->next;
        }

使用虚拟头节点：

1
2
3
4
ListNode* dummyHead=new ListNode(-1);
dummyHead->next=head
//使原先的头节点失去特殊地位
//最后记得要返回dummyHead->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 *dummyHead=new ListNode(-1);
        dummyHead->next=head;
        auto vi=dummyHead;
        while(vi->next!=nullptr)
        {
            if(vi->next->val==val){
                auto tmp=vi->next;
                vi->next=tmp->next;
                delete tmp;
            }
            else
                vi=vi->next;
        }
        head=dummyHead->next;
        delete dummyHead;
        return head;
    }
};

反转链表

反转链表I

https://leetcodereverse-linked-list/

双指针法

pre与cur指针

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre=nullptr,*cur=head;
        while(cur){
            ListNode* temp=cur->next;//保存cur->next，因为它会被更改
            cur->next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;//新的头节点
    }
};
递归法
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return rev(head,NULL);
    }
private:
    ListNode* rev(ListNode* cur,ListNode* pre){
        if(cur==nullptr)	return pre;
        auto temp=cur->next;
        cur->next=pre;
        return rev(temp,cur);//相当于pre=cur;cur=temp;
    }
};

反转链表II

leetcode.com/problems…

截断

截断待反转的区域，将它反转再重新插入

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
class Solution {
private:
    void rev(ListNode *head)
    {
    	ListNode *cur=head,*pre=nullptr;
        while(cur){
            auto tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        }
    }
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(right==left)  return head;
        ListNode *dummyHead=new ListNode(-1);
        dummyHead->next=head;
        ListNode *pre=dummyHead,*rtnode,*ltnode,*nex;
        for(int i=0;i<left-1;++i){
            pre=pre->next;
        }
        ltnode=pre->next;
        rtnode=ltnode;
        for(int i=0;i<right-left;++i){
            rtnode=rtnode->next;
        }
        nex=rtnode->next;
        /*至此已获得四个需要的指针: pre, ltnode, rtnode, nex*/
        
        //截断
		pre->next=NULL;
        rtnode->next=NULL;
        
        //反转
        rev(ltnode);
        //插回
        
        pre->next=rtnode;
        ltnode->next=nex;
        return dummyHead->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* reverseBetween(ListNode* head, int left, int right) {
        if(left==right) return head;
        ListNode* dummyNode=new ListNode(-1);
        dummyNode->next=head;
        ListNode *cur,*Next,*pre=dummyNode;
        for(int i=0;i<left-1;++i){
            pre=pre->next;
        }
        cur=pre->next;
        for(int i=0;i<right-left;++i){
            Next=cur->next;
            cur->next=Next->next;
            Next->next=pre->next;
            pre->next=Next;
        }
        return dummyNode->next;
    }
};

环

leetcode环形链表

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;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast=head,*slow=head;
        while(fast&&fast->next)
        {
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow){
                ListNode *ind1=head,*ind2=fast;
                while(ind1!=ind2){
                    ind1=ind1->next;
                    ind2=ind2->next;
                }
                return ind1;
            }
        }
        return 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
//非递归
class Solution {
    
public:
    ListNode* sortList(ListNode* head) {
        ListNode* dummyHead=new ListNode;
        dummyHead->next=head;
        int len=0;
        ListNode* p=head;
        while(p)
        {
            ++len;
            p=p->next;
        }
        for(int i=1;i<len;i<<=1)
        {
            ListNode* cur=dummyHead->next;
            ListNode* tail=dummyHead;
            while(cur)
            {
                auto left=cur;
                auto right=cut(left,i);
                cur=cut(right,i);
                tail->next=merge(left,right);
                while(tail->next) tail=tail->next;
            }
        }
        auto ret=dummyHead->next;
        delete dummyHead;
        return ret;
    }
    
private:

    ListNode* cut(ListNode* head,int n)
    {
        ListNode* cur=head;
        while(--n && cur)
            cur=cur->next;
        if(!cur) return nullptr;
        ListNode* ret=cur->next;
        cur->next=nullptr;
        return ret;
    }

    ListNode* merge(ListNode* left,ListNode* right)
    {
        ListNode* dummyHead=new ListNode;
        ListNode* p=dummyHead;
        while(left && right)
        {
            if(left->val<right->val)
            {
                p->next=left;
                p=left;
                left=left->next;
            }
            else 
            {
                p->next=right;
                p=right;
                right=right->next;
            }
        }
        p->next= left ? left : right;
        auto ret=dummyHead->next;
        delete dummyHead;
        return ret;
    }
};

计算PI

利用反三角函数幂级展开式进行计算

经计算，取n = 2000可以保证前550位的精度

模拟大数运算

乘法

从尾至头做乘法，处理进位。若有溢出，可在链表头部添加节点，也可以不加。

1、添加节点后，增加的是整数位，小数点后位数不变，由于乘发结束后要除以一个更大的数

（即2*i-1 > i - 1），整数位均变为0，执行加法时，从两链表尾部开始遍历，到短链表头处终止即可，前面整数部分的零无需参与加法运算。

2、不添加节点，整数位会大于10，同理，做除法后整数位必定为零，因此只需处理第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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include<iostream>
using namespace std;

//双向链表
struct LinkedNode
{
    int val;
    LinkedNode* next;
    LinkedNode* pre;
    //设置尾节点，便于倒序遍历
    LinkedNode* tail;
    LinkedNode() : val(0), next(nullptr), pre(nullptr), tail(this) { }
    LinkedNode(int val) : val(val), next(nullptr), 
    pre(nullptr), tail(this) { }
};

using Lptr = LinkedNode*;

//高精度计算类
class Caculation
{
public:
    //重载+、*、/
    void operator+(Caculation& cal);
    void operator*(int val);
    void operator/(int val);
    //输出前n位
    void print(int n);
    //初始化函数
    void init();
    //初始化存放结果的链表
    void initRet();
    Caculation() {
        init();
    }
    Caculation(int) {
        initRet();
    }
    //获取p
    Lptr getP() {return p;}
private:
    //此为头节点
    Lptr p;
};


// 求前550位
const int Max = 550;

int main()
{
    int n;
    scanf("%d", &n);
    Caculation result(1), head;
    for(int i = 2; i <= 2000; ++i)
    {
        head * (i - 1);
        head / ((i << 1) - 1);
        result + head;
    }
    result * 2;
    result.print(n);
    return 0;
}

void Caculation::init()
{
    p = new LinkedNode(0);
    auto q = new LinkedNode(1);
    q->pre = p;
    p->next = q;
    p->tail = q;
}

void Caculation::initRet()
{
    p = new LinkedNode(0);
    auto L = p;
    for(int i = 0; i <= Max; ++i)
    {
        auto cur = new LinkedNode(0);
        cur->pre = L;
        L->next = cur;
        L = cur;
    }
    p->next->val = 1;
    p->tail = L;
}

void Caculation::print(int n)
{
    auto cur = p->next;
    printf("%d.", cur->val);
    cur = cur->next;
    for(int i = 0; i < n; ++i)
    {
        printf("%d",cur->val);
        cur = cur->next;
    }
}

void Caculation::operator+(Caculation& cal)
{
    auto p2 = cal.getP();
    Lptr t1 = this->p->tail, t2 = p2->tail;
    while(t1 != this->p && t2 != p2)
    {
        t1->val += t2->val;
        t1->pre->val += t1->val / 10;
        t1->val %= 10;
        t1 = t1->pre;
        t2 = t2->pre;
    }
}

void Caculation::operator/(int val)
{
    //进位
    int carry(0);
    //位数
    int len(0);
    auto cur = p->next;
    //记录前一位
    Lptr pre;
    //模拟除法
    while(cur)
    {
        cur->val += carry * 10;
        carry = cur->val % val;
        cur->val /= val;
        pre = cur;
        cur = cur->next;
        ++len;
    }
    //回退
    cur = pre;
    while(carry && len <= Max)
    {
        auto newNode = new LinkedNode(0);
        newNode->val = carry * 10;
        newNode->pre = cur;
        carry = newNode->val % val;
        cur->next = newNode;
        newNode->val /= val;
        cur->next = newNode;
        cur = newNode;
        ++len;
    }
    p->tail = cur;
}

void Caculation::operator*(int val)
{
    Lptr cur = p->tail;
    //先做乘法
    while(cur != p)
    {
        cur->val *= val;
        cur = cur->pre;
    }
    //再处理进位
    cur = p->tail;
    while(cur != p->next)
    {
        cur->pre->val += cur->val / 10;
        cur->val %= 10;
        cur = cur->pre;
    }
    //可添加节点
    while(cur->val >= 10)
    {
        auto newNode = new LinkedNode(0);
        newNode->val = cur->val / 10;
        cur->val %= 10;
        newNode->pre = p;
        newNode->next = cur;
        p->next = newNode;
        cur->pre = newNode;
        cur = newNode;
    }
}