链表

1、单链表的建立

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode
 6 {
 7 public:
 8     int val;
 9     ListNode *next;
10     ListNode(){}
11     ListNode(int x):val(x),next(nullptr){}
12 };
13 
14 void printList(ListNode* list)
15 {
16     if (list == nullptr)
17         return;
18     ListNode* p = list;
19     while (p)
20     {
21         cout << p->val << " ";
22         p = p->next;
23     }
24     cout << endl;
25 }
26 
27 ListNode *createList()
28 {
29     int in;
30     cout << "enter list value (enter 100 to quit):";
31     cin >> in;
32     ListNode *head = nullptr;
33     if (in == 100)
34         return head;
35     else
36     {
37         head = new ListNode(in);
38         head->next = createList();
39     }
40     return head;
41 }
42 
43 int main()
44 {
45     ListNode* list = createList();
46     printList(list);
47 
48     return 0;
49 }

View Code

2、求单链表的长度

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode
 6 {
 7 public:
 8     int val;
 9     ListNode *next;
10     ListNode(){}
11     ListNode(int x):val(x),next(nullptr){}
12 };
13 
14 ListNode *createList()
15 {
16     int in;
17     cout << "enter list value (enter 100 to quit):";
18     cin >> in;
19     ListNode *head = nullptr;
20     if (in == 100)
21         return head;
22     else
23     {
24         head = new ListNode(in);
25         head->next = createList();
26     }
27     return head;
28 }
29 
30 int getLength(ListNode* list)
31 {
32     if (list == nullptr)
33         return 0;
34     int len = 0;
35     ListNode* p = list;
36     while (p)
37     {
38         ++len;
39         p = p->next;
40     }
41     return len;
42 }
43 
44 int main()
45 {
46     ListNode* list = createList();
47     cout << getLength(list) << endl;
48 
49     return 0;
50 }

View Code

3、单链表的插入

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode
 6 {
 7 public:
 8     int val;
 9     ListNode *next;
10     ListNode(){}
11     ListNode(int x):val(x),next(nullptr){}
12 };
13 
14 void printList(ListNode* list)
15 {
16     if (list == nullptr)
17         return;
18     ListNode* p = list;
19     while (p)
20     {
21         cout << p->val << " ";
22         p = p->next;
23     }
24     cout << endl;
25 }
26 
27 ListNode *createList()
28 {
29     int in;
30     cout << "enter list value (enter 100 to quit):";
31     cin >> in;
32     ListNode *head = nullptr;
33     if (in == 100)
34         return head;
35     else
36     {
37         head = new ListNode(in);
38         head->next = createList();
39     }
40     return head;
41 }
42 
43 void insertNode(ListNode* head, int val, int pos)
44 {
45     if (head == nullptr)
46         return;
47     ListNode *node = new ListNode(val);
48     ListNode* p = head;
49     ListNode* last = head;
50     if (pos == 0)
51     {
52         node->val = head->val;
53         head->val = val;
54         node->next = head->next;
55         head->next = node;
56     }
57     else
58     {
59         int index = 1;
60         while (p&&index < pos)
61         {
62             ++index;
63             p = p->next;
64         }
65         if (p)
66         {
67             node->next = p->next;
68             p->next = node;
69         }
70         else
71         {
72             while (last->next)
73                 last = last->next;
74             last->next = node;
75         }
76     }
77 }
78 
79 int main()
80 {
81     ListNode* list = createList();
82     printList(list);    
83     insertNode(list, 5, 3);
84     printList(list);
85     ListNode* head = nullptr;
86     insertNode(head, 5, 3);
87 
88     return 0;
89 }

View Code

4、单链表的删除

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode
 6 {
 7 public:
 8     int val;
 9     ListNode *next;
10     ListNode(){}
11     ListNode(int x):val(x),next(nullptr){}
12 };
13 
14 void printList(ListNode* list)
15 {
16     if (list == nullptr)
17         return;
18     ListNode* p = list;
19     while (p)
20     {
21         cout << p->val << " ";
22         p = p->next;
23     }
24     cout << endl;
25 }
26 
27 ListNode *createList()
28 {
29     int in;
30     cout << "enter list value (enter 100 to quit):";
31     cin >> in;
32     ListNode *head = nullptr;
33     if (in == 100)
34         return head;
35     else
36     {
37         head = new ListNode(in);
38         head->next = createList();
39     }
40     return head;
41 }
42 
43 void deleteNode(ListNode* head, ListNode* node)
44 {
45     if (head == nullptr||node==nullptr)
46         return;
47     if (head == node)
48     {
49         head->val = head->next->val;
50         head->next = head->next->next;
51     }
52     else if (node->next)
53     {
54         ListNode *p = node->next;
55         node->val = p->val;
56         node->next = p->next;
57     }
58     else
59     {
60         ListNode* p = head;
61         while (p)
62         {
63             if (p->next == node)
64                 p->next = nullptr;
65             p = p->next;
66         }
67     }
68 }
69 
70 int main()
71 {
72     ListNode* list = createList();
73     printList(list);
74     ListNode* node = list;
75     deleteNode(list, node);
76     printList(list);
77     ListNode* node2 = list->next->next;
78     deleteNode(list, node2);
79     printList(list);
80     ListNode* last = list;
81     while (last->next)
82         last = last->next;
83     deleteNode(list, last);
84     printList(list);
85     
86 
87     return 0;
88 }

View Code

5、查找单链表的第i个结点

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode
 6 {
 7 public:
 8     int val;
 9     ListNode *next;
10     ListNode(){}
11     ListNode(int x):val(x),next(nullptr){}
12 };
13 
14 void printList(ListNode* list)
15 {
16     if (list == nullptr)
17         return;
18     ListNode* p = list;
19     while (p)
20     {
21         cout << p->val << " ";
22         p = p->next;
23     }
24     cout << endl;
25 }
26 
27 ListNode *createList()
28 {
29     int in;
30     cout << "enter list value (enter 100 to quit):";
31     cin >> in;
32     ListNode *head = nullptr;
33     if (in == 100)
34         return head;
35     else
36     {
37         head = new ListNode(in);
38         head->next = createList();
39     }
40     return head;
41 }
42 
43 ListNode* findKNode(ListNode* head, int k)
44 {
45     if (head == nullptr || k < 0)
46         return nullptr;
47     if (k == 0)
48         return head;
49     ListNode* p = head;
50     while (k--)
51     {
52         p = p->next;
53         if (p == nullptr)
54         {
55             cout << "Incorrect position to search node!" << endl;
56             break;
57         }
58     }
59     return p;
60 }
61 
62 int main()
63 {
64     ListNode* list = createList();
65     printList(list);
66     cout << findKNode(list, 3)->val << endl;        
67 
68     return 0;
69 }

View Code

6、查找单链表的中间节点

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode
 6 {
 7 public:
 8     int val;
 9     ListNode *next;
10     ListNode(){}
11     ListNode(int x):val(x),next(nullptr){}
12 };
13 
14 void printList(ListNode* list)
15 {
16     if (list == nullptr)
17         return;
18     ListNode* p = list;
19     while (p)
20     {
21         cout << p->val << " ";
22         p = p->next;
23     }
24     cout << endl;
25 }
26 
27 ListNode *createList()
28 {
29     int in;
30     cout << "enter list value (enter 100 to quit):";
31     cin >> in;
32     ListNode *head = nullptr;
33     if (in == 100)
34         return head;
35     else
36     {
37         head = new ListNode(in);
38         head->next = createList();
39     }
40     return head;
41 }
42 
43 ListNode* findMidNode(ListNode* head)
44 {
45     if (head == nullptr)
46         return nullptr;
47     ListNode* slow = head;
48     ListNode* fast = head;
49     while (fast&&fast->next)
50     {
51         slow = slow->next;
52         fast = fast->next->next;
53     }
54     return slow;
55 }
56 
57 int main()
58 {
59     ListNode* list = createList();
60     printList(list);
61     cout << findMidNode(list)->val << endl;        
62 
63     return 0;
64 }

View Code

7、查找单链表中倒数第k个元素

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode
 6 {
 7 public:
 8     int val;
 9     ListNode *next;
10     ListNode(){}
11     ListNode(int x):val(x),next(nullptr){}
12 };
13 
14 void printList(ListNode* list)
15 {
16     if (list == nullptr)
17         return;
18     ListNode* p = list;
19     while (p)
20     {
21         cout << p->val << " ";
22         p = p->next;
23     }
24     cout << endl;
25 }
26 
27 ListNode *createList()
28 {
29     int in;
30     cout << "enter list value (enter 100 to quit):";
31     cin >> in;
32     ListNode *head = nullptr;
33     if (in == 100)
34         return head;
35     else
36     {
37         head = new ListNode(in);
38         head->next = createList();
39     }
40     return head;
41 }
42 
43 ListNode* findLastKNode(ListNode* head,int k)
44 {
45     if (head == nullptr||k<0)
46         return nullptr;
47     ListNode* p1 = head;
48     ListNode* p2 = head;
49     for (int i = 0; i < k; ++i)
50     {
51         if (p1->next)
52             p1 = p1->next;
53         else
54             return nullptr;
55     }
56     while (p1->next)
57     {
58         p1 = p1->next;
59         p2 = p2->next;
60     }
61     return p2;
62 }
63 
64 int main()
65 {
66     ListNode* list = createList();
67     printList(list);
68     cout << findLastKNode(list,3)->val << endl;        
69 
70     return 0;
71 }

View Code

8、单链表反转

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode
 6 {
 7 public:
 8     int val;
 9     ListNode *next;
10     ListNode(){}
11     ListNode(int x):val(x),next(nullptr){}
12 };
13 
14 void printList(ListNode* list)
15 {
16     if (list == nullptr)
17         return;
18     ListNode* p = list;
19     while (p)
20     {
21         cout << p->val << " ";
22         p = p->next;
23     }
24     cout << endl;
25 }
26 
27 ListNode *createList()
28 {
29     int in;
30     cout << "enter list value (enter 100 to quit):";
31     cin >> in;
32     ListNode *head = nullptr;
33     if (in == 100)
34         return head;
35     else
36     {
37         head = new ListNode(in);
38         head->next = createList();
39     }
40     return head;
41 }
42 
43 ListNode* reverseList(ListNode* head)
44 {
45     if (head == nullptr)
46         return head;
47     ListNode* cur = head;
48     ListNode* pre = nullptr;
49     ListNode* next = nullptr;
50     while (cur)
51     {
52         next = cur->next;
53         cur->next = pre;
54         pre = cur;
55         cur = next;
56     }
57     return pre;
58 }
59 
60 int main()
61 {
62     ListNode* list = createList();
63     printList(list);
64     ListNode *res = reverseList(list);
65     printList(res);
66 
67     return 0;
68 }

View Code

9、逆序输出单链表元素

 1 #include<iostream>
 2 #include<stack>
 3 
 4 using namespace std;
 5 
 6 class ListNode
 7 {
 8 public:
 9     int val;
10     ListNode *next;
11     ListNode(){}
12     ListNode(int x):val(x),next(nullptr){}
13 };
14 
15 void printList(ListNode* list)
16 {
17     if (list == nullptr)
18         return;
19     ListNode* p = list;
20     while (p)
21     {
22         cout << p->val << " ";
23         p = p->next;
24     }
25     cout << endl;
26 }
27 
28 ListNode *createList()
29 {
30     int in;
31     cout << "enter list value (enter 100 to quit):";
32     cin >> in;
33     ListNode *head = nullptr;
34     if (in == 100)
35         return head;
36     else
37     {
38         head = new ListNode(in);
39         head->next = createList();
40     }
41     return head;
42 }
43 
44 void reversePrintList(ListNode* head)
45 {
46     if (head == nullptr)
47         return;
48     stack<ListNode*> stk;
49     ListNode* p = head;
50     while (p)
51     {
52         stk.push(p);
53         p = p->next;
54     }
55     while (!stk.empty())
56     {
57         p = stk.top();
58         stk.pop();
59         cout << p->val << " ";
60     }
61     cout << endl;
62 }
63 
64 int main()
65 {
66     ListNode* list = createList();
67     printList(list);
68     reversePrintList(list);
69 
70     return 0;
71 }

View Code

10、判断单链表是否存在环

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode
 6 {
 7 public:
 8     int val;
 9     ListNode* next;
10     ListNode(){}
11     ListNode(int x):val(x),next(nullptr){}
12 };
13 
14 ListNode* createList()
15 {
16     int in;
17     cout << "enter list value (enter 100 to quit):";
18     cin >> in;
19     ListNode* head = nullptr;
20     if (in == 100)
21         return head;
22     else
23     {
24         head = new ListNode(in);
25         head->next = createList();
26     }
27     return head;
28 }
29 
30 bool hasCycle(ListNode* head)
31 {
32     if (head == nullptr)
33         return false;
34     ListNode* slow = head;
35     ListNode* fast = head;
36     while (fast&&fast->next)
37     {
38         slow = slow->next;
39         fast = fast->next->next;
40         if (slow == fast)
41             return true;
42     }
43     return false;
44 }
45 
46 int main()
47 {
48     ListNode* head = createList();
49     ListNode* node = head->next->next->next;
50     ListNode* last = head;
51     while (last->next)
52         last = last->next;
53     last->next = node;
54     cout << hasCycle(head) << endl;
55 
56     return 0;
57 }

View Code

11、求环的长度

第一次相遇后，让fast停着不走了，slow继续走，记录到下次相遇时循环了几次。

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode
 6 {
 7 public:
 8     int val;
 9     ListNode* next;
10     ListNode(){}
11     ListNode(int x):val(x),next(nullptr){}
12 };
13 
14 ListNode* createList()
15 {
16     int in;
17     cout << "enter list value (enter 100 to quit):";
18     cin >> in;
19     ListNode* head = nullptr;
20     if (in == 100)
21         return head;
22     else
23     {
24         head = new ListNode(in);
25         head->next = createList();
26     }
27     return head;
28 }
29 
30 int getCycleLength(ListNode* head)
31 {
32     if (head == nullptr)
33         return 0;
34     ListNode* slow = head;
35     ListNode* fast = head;
36     while (fast&&fast->next)
37     {
38         slow = slow->next;
39         fast = fast->next->next;
40         if (slow == fast)
41             break;
42     }
43     int len = 1;
44     ListNode* p = slow->next;
45     while (p != fast)
46     {
47         ++len;
48         p = p->next;
49     }
50     return len;
51 }
52 
53 int main()
54 {
55     ListNode* head = createList();
56     ListNode* node = head->next->next->next;
57     ListNode* last = head;
58     while (last->next)
59         last = last->next;
60     last->next = node;
61     cout << getCycleLength(head) << endl;
62 
63     return 0;
64 }

View Code

12、求有环单链表的长度

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode
 6 {
 7 public:
 8     int val;
 9     ListNode* next;
10     ListNode(){}
11     ListNode(int x):val(x),next(nullptr){}
12 };
13 
14 ListNode* createList()
15 {
16     int in;
17     cout << "enter list value (enter 100 to quit):";
18     cin >> in;
19     ListNode* head = nullptr;
20     if (in == 100)
21         return head;
22     else
23     {
24         head = new ListNode(in);
25         head->next = createList();
26     }
27     return head;
28 }
29 
30 int getLength(ListNode* head)
31 {
32     if (head == nullptr)
33         return 0;
34     ListNode* slow = head;
35     ListNode* fast = head;
36     ListNode* last = nullptr;
37     ListNode* mid = nullptr;
38     bool flag = false;
39     while (fast&&fast->next)
40     {
41         slow = slow->next;
42         fast = fast->next->next;
43         if (slow == fast)
44         {
45             mid = slow->next;
46             last = fast;
47             fast = head;
48             while (slow != fast)
49             {
50                 slow = slow->next;
51                 fast = fast->next;
52                 if (slow == fast)
53                     flag = true;
54             }
55         }
56         if (flag)
57             break;
58     }
59     ListNode* start = head;
60     ListNode* end = slow;
61     int len = 0;
62     while (start != end)
63     {
64         ++len;
65         start = start->next;
66     }
67     ++len;
68     while (mid != last)
69     {
70         ++len;
71         mid = mid->next;
72     }
73     return len;
74 }
75 
76 int main()
77 {
78     ListNode* head = createList();
79     ListNode* node = head->next->next->next;
80     ListNode* last = head;
81     while (last->next)
82         last = last->next;
83     last->next = node;
84     cout << getLength(head) << endl;
85 
86     return 0;
87 }

View Code

13、求环的入口结点

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode
 6 {
 7 public:
 8     int val;
 9     ListNode* next;
10     ListNode(){}
11     ListNode(int x):val(x),next(nullptr){}
12 };
13 
14 ListNode* createList()
15 {
16     int in;
17     cout << "enter list value (enter 100 to quit):";
18     cin >> in;
19     ListNode* head = nullptr;
20     if (in == 100)
21         return head;
22     else
23     {
24         head = new ListNode(in);
25         head->next = createList();
26     }
27     return head;
28 }
29 
30 ListNode* findCycleNode(ListNode* head)
31 {
32     if (head == nullptr)
33         return false;
34     ListNode* slow = head;
35     ListNode* fast = head;
36     while (fast&&fast->next)
37     {
38         slow = slow->next;
39         fast = fast->next->next;
40         if (slow == fast)
41         {
42             fast = head;
43             while (slow != fast)
44             {
45                 slow = slow->next;
46                 fast = fast->next;
47             }
48             return slow;
49         }
50     }
51     return nullptr;
52 }
53 
54 int main()
55 {
56     ListNode* head = createList();
57     ListNode* node = head->next->next->next;
58     ListNode* last = head;
59     while (last->next)
60         last = last->next;
61     last->next = node;
62     cout << findCycleNode(head)->val << endl;
63 
64     return 0;
65 }

View Code

14、合并两个有序单链表

（1）非递归

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode
 6 {
 7 public:
 8     int val;
 9     ListNode* next;
10     ListNode() {}
11     ListNode(int x) :val(x), next(nullptr) {}
12 };
13 
14 ListNode* createList()
15 {
16     int in;
17     cout << "enter list value (enter 100 to quit):";
18     cin >> in;
19     ListNode* head = nullptr;
20     if (in == 100)
21         return head;
22     else
23     {
24         head = new ListNode(in);
25         head->next = createList();
26     }
27     return head;
28 }
29 
30 void printList(ListNode* head)
31 {
32     if (head == nullptr)
33         return;
34     ListNode* p = head;
35     while (p)
36     {
37         cout << p->val << " ";
38         p = p->next;
39     }
40     cout << endl;
41 }
42 
43 ListNode* mergeList(ListNode* list1, ListNode* list2)
44 {
45     if (!list1 && !list2)
46         return nullptr;
47     if (!list1)
48         return list2;
49     if (!list2)
50         return list1;
51     ListNode* first = new ListNode(-1);
52     ListNode* cur = first;
53     while (list1&&list2)
54     {
55         if (list1->val < list2->val)
56         {
57             cur->next = list1;
58             list1 = list1->next;
59         }
60         else
61         {
62             cur->next = list2;
63             list2 = list2->next;
64         }
65         cur = cur->next;
66     }
67     cur->next = list1 ? list1 : list2;
68     return first->next;
69 }
70 
71 int main()
72 {
73     ListNode* node1 = createList();
74     printList(node1);
75     ListNode* node2 = createList();
76     printList(node2);
77     ListNode* res = mergeList(node1, node2);
78     printList(res);
79 
80     return 0;
81 }

View Code

（2）递归

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode
 6 {
 7 public:
 8     int val;
 9     ListNode* next;
10     ListNode() {}
11     ListNode(int x) :val(x), next(nullptr) {}
12 };
13 
14 ListNode* createList()
15 {
16     int in;
17     ListNode* head = nullptr;
18     cout << "enter list val (enter 100 to quit):";
19     cin >> in;
20     if (in == 100)
21         return head;
22     else
23     {
24         head = new ListNode(in);
25         head->next = createList();
26     }
27     return head;
28 }
29 
30 void printNode(ListNode* head)
31 {
32     ListNode* p = head;
33     while (p)
34     {
35         cout << p->val << " ";
36         p = p->next;
37     }
38     cout << endl;
39 }
40 
41 ListNode* mergeListRecur(ListNode* list1, ListNode* list2)
42 {
43     if (!list1 && !list2)
44         return nullptr;
45     if (list1 == nullptr)
46         return list2;
47     if (list2 == nullptr)
48         return list1;
49     ListNode* head = nullptr;
50     if (list1->val < list2->val)
51     {
52         head = list1;
53         head->next = mergeListRecur(list1->next, list2);
54     }
55     else
56     {
57         head = list2;
58         head->next = mergeListRecur(list1, list2->next);
59     }
60     return head;
61 }
62 
63 int main()
64 {
65     ListNode* head1 = createList();
66     ListNode* head2 = createList();
67     printNode(head1);
68     printNode(head2);
69     ListNode* head = mergeListRecur(head1, head2);
70     printNode(head);
71 
72     return 0;
73 }

View Code

15、删除单链表的重复结点

（1）保留一个重复的结点

递归实现：

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode {
 6 public:
 7     int val;
 8     ListNode* next;
 9     ListNode() {}
10     ListNode(int x) :val(x), next(nullptr) {}
11 };
12 
13 void printListNode(ListNode* head)
14 {
15     ListNode* cur = head;
16     while (cur)
17     {
18         cout << cur->val << " ";
19         cur = cur->next;
20     }
21     cout << endl;
22 }
23 
24 ListNode* createListNode()
25 {
26     int in;
27     ListNode* head = nullptr;
28     cout << "enter list val (enter 100 to quit):";
29     cin >> in;
30     if (in == 100)
31         return head;
32     else
33     {
34         head = new ListNode(in);
35         head->next = createListNode();
36     }
37     return head;
38 }
39 
40 ListNode* deleteRepeateNode(ListNode* head)
41 {
42     if (head == nullptr)
43         return nullptr;
44     if (head != nullptr&&head->next == nullptr)
45         return head;
46     ListNode* tmp = head;
47     ListNode* next = deleteRepeateNode(head->next);
48     if (next)
49         if (tmp->val == next->val)
50             tmp->next = next->next;
51     return head;
52 }
53 
54 int main()
55 {
56     ListNode* head = createListNode();
57     printListNode(head);
58     printListNode(deleteRepeateNode(head));
59 
60     return 0;
61 }

View Code

非递归实现：

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode {
 6 public:
 7     int val;
 8     ListNode* next;
 9     ListNode() {}
10     ListNode(int x) :val(x), next(nullptr) {}
11 };
12 
13 void printListNode(ListNode* head)
14 {
15     ListNode* cur = head;
16     while (cur)
17     {
18         cout << cur->val << " ";
19         cur = cur->next;
20     }
21     cout << endl;
22 }
23 
24 ListNode* createListNode()
25 {
26     int in;
27     ListNode* head = nullptr;
28     cout << "enter list val (enter 100 to quit):";
29     cin >> in;
30     if (in == 100)
31         return head;
32     else
33     {
34         head = new ListNode(in);
35         head->next = createListNode();
36     }
37     return head;
38 }
39 
40 ListNode* deleteRepeateNode(ListNode* head)
41 {
42     ListNode* cur = head;
43     while (cur)
44     {
45         while (cur->next&&cur->val==cur->next->val)
46             cur->next = cur->next->next;
47         cur = cur->next;
48     }
49     return head;
50 }
51 
52 int main()
53 {
54     ListNode* head = createListNode();
55     printListNode(head);
56     printListNode(deleteRepeateNode(head));
57 
58     return 0;
59 }

View Code

（2）不保留重复结点

递归实现：

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode {
 6 public:
 7     int val;
 8     ListNode* next;
 9     ListNode() {}
10     ListNode(int x) :val(x), next(nullptr) {}
11 };
12 
13 void printListNode(ListNode* head)
14 {
15     ListNode* cur = head;
16     while (cur)
17     {
18         cout << cur->val << " ";
19         cur = cur->next;
20     }
21     cout << endl;
22 }
23 
24 ListNode* createListNode()
25 {
26     int in;
27     ListNode* head = nullptr;
28     cout << "enter list val (enter 100 to quit):";
29     cin >> in;
30     if (in == 100)
31         return head;
32     else
33     {
34         head = new ListNode(in);
35         head->next = createListNode();
36     }
37     return head;
38 }
39 
40 ListNode* deleteRepeateNode(ListNode* head)
41 {
42     if (!head || head && !head->next)
43         return head;
44     ListNode* cur = nullptr;
45     if (head->val == head->next->val)
46     {
47         cur = head->next;
48         while (cur&&cur->val == head->val)
49             cur = cur->next;
50         return deleteRepeateNode(cur);
51     }
52     else
53     {
54         cur = head->next;
55         head->next = deleteRepeateNode(cur);
56         return head;
57     }
58 }
59 
60 int main()
61 {
62     ListNode* head = createListNode();
63     printListNode(head);
64     printListNode(deleteRepeateNode(head));
65 
66     return 0;
67 }

View Code

非递归实现：

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode {
 6 public:
 7     int val;
 8     ListNode* next;
 9     ListNode() {}
10     ListNode(int x) :val(x), next(nullptr) {}
11 };
12 
13 void printListNode(ListNode* head)
14 {
15     ListNode* cur = head;
16     while (cur)
17     {
18         cout << cur->val << " ";
19         cur = cur->next;
20     }
21     cout << endl;
22 }
23 
24 ListNode* createListNode()
25 {
26     int in;
27     ListNode* head = nullptr;
28     cout << "enter list val (enter 100 to quit):";
29     cin >> in;
30     if (in == 100)
31         return head;
32     else
33     {
34         head = new ListNode(in);
35         head->next = createListNode();
36     }
37     return head;
38 }
39 
40 ListNode* deleteRepeateNode(ListNode* head)
41 {
42     ListNode* first = new ListNode(-1);
43     first->next = head;
44     ListNode* p = head;
45     ListNode* last = first;
46     while (p&&p->next)
47     {
48         if (p->val == p->next->val)
49         {
50             int val = p->val;
51             while (p&&p->val == val)
52                 p = p->next;
53             last->next = p;
54         }
55         else
56         {
57             last = p;
58             p = p->next;
59         }
60     }
61     return first->next;
62 }
63 
64 int main()
65 {
66     ListNode* head = createListNode();
67     printListNode(head);
68     printListNode(deleteRepeateNode(head));
69 
70     return 0;
71 }

View Code

16、判断两个链表是否交叉

单链表相交是指两个链表存在完全相同的部分（不是相交与一个结点）

判断单链表相交有两种方法：
方法一：将两个链表的首尾相连，监测是否有环

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode {
 6 public:
 7     int val;
 8     ListNode* next;
 9     ListNode() {}
10     ListNode(int x) :val(x), next(nullptr) {}
11 };
12 
13 void printListNode(ListNode* head)
14 {
15     ListNode* cur = head;
16     while (cur)
17     {
18         cout << cur->val << " ";
19         cur = cur->next;
20     }
21     cout << endl;
22 }
23 
24 ListNode* createListNode()
25 {
26     int in;
27     ListNode* head = nullptr;
28     cout << "enter list val (enter 100 to quit):";
29     cin >> in;
30     if (in == 100)
31         return head;
32     else
33     {
34         head = new ListNode(in);
35         head->next = createListNode();
36     }
37     return head;
38 }
39 
40 bool helper(ListNode *head)
41 {
42     if (head == nullptr || head->next == nullptr || head->next->next == nullptr)
43         return head;
44     ListNode *slow = head;
45     ListNode *fast = head;
46     while (fast&&fast->next)
47     {
48         slow = slow->next;
49         fast = fast->next->next;
50         if (slow == fast)
51             return true;
52     }
53     return false;
54 }
55 
56 bool isY(ListNode *f, ListNode *s)
57 {
58     if (f == nullptr || s == nullptr)
59         return false;
60     while (s->next)
61         s = s->next;
62     s->next = f;
63     return helper(s);
64 }
65 
66 int main()
67 {
68     ListNode* head1 = createListNode();
69     printListNode(head1);
70     ListNode* node = head1->next->next->next;
71     ListNode* head2 = createListNode();
72     ListNode* last = head2;
73     while (last->next)
74         last = last->next;
75     last->next = node;
76     printListNode(head2);
77     cout << isY(head1, head2) << endl;
78 
79     return 0;
80 }

View Code

方法二：如两个单链表相交，那么从相交结点开始到链表结束都是相同的结点，必然是Y字形，判断两个链表的最后一个结点是否相同即可。

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode {
 6 public:
 7     int val;
 8     ListNode* next;
 9     ListNode() {}
10     ListNode(int x) :val(x), next(nullptr) {}
11 };
12 
13 void printListNode(ListNode* head)
14 {
15     ListNode* cur = head;
16     while (cur)
17     {
18         cout << cur->val << " ";
19         cur = cur->next;
20     }
21     cout << endl;
22 }
23 
24 ListNode* createListNode()
25 {
26     int in;
27     ListNode* head = nullptr;
28     cout << "enter list val (enter 100 to quit):";
29     cin >> in;
30     if (in == 100)
31         return head;
32     else
33     {
34         head = new ListNode(in);
35         head->next = createListNode();
36     }
37     return head;
38 }
39 
40 bool isY(ListNode *f, ListNode *s)
41 {
42     if (f == nullptr || s == nullptr)
43         return false;
44     ListNode* cur1 = f;
45     ListNode* cur2 = s;
46     while (cur1->next)
47         cur1 = cur1->next;
48     while (cur2->next)
49         cur2 = cur2->next;
50     if (cur1 == cur2)
51         return true;
52     return false;
53 }
54 
55 int main()
56 {
57     ListNode* head1 = createListNode();
58     printListNode(head1);
59     ListNode* node = head1->next->next->next;
60     ListNode* head2 = createListNode();
61     ListNode* last = head2;
62     while (last->next)
63         last = last->next;
64     last->next = node;
65     printListNode(head2);
66     cout << isY(head1, head2) << endl;
67 
68     return 0;
69 }

View Code

17、交换单链表中任意两个结点

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 class ListNode {
 6 public:
 7     int val;
 8     ListNode* next;
 9     ListNode() {}
10     ListNode(int x) :val(x), next(nullptr) {}
11 };
12 
13 void printListNode(ListNode* head)
14 {
15     ListNode* cur = head;
16     while (cur)
17     {
18         cout << cur->val << " ";
19         cur = cur->next;
20     }
21     cout << endl;
22 }
23 
24 ListNode* findPreNode(ListNode* head, ListNode* node)
25 {
26     if (head == nullptr || node == nullptr)
27         return nullptr;
28     ListNode* p = head;
29     while (p)
30         if (p->next == node)
31             return p;
32         else
33             p = p->next;
34     return nullptr;
35 }
36 
37 ListNode* exchangeTwoNode(ListNode* head, ListNode* node1, ListNode* node2)
38 {
39     if (head == nullptr || node1 == nullptr || node2 == nullptr)
40         return head;
41     if (node1->val == node2->val)
42         return head;
43     if (node1->next == node2)
44     {
45         ListNode* pre = findPreNode(head, node1);
46         pre->next = node2;
47         node1->next = node2->next;
48         node2->next = node1;
49     }
50     else if (node2->next == node1)
51     {
52         ListNode* pre = findPreNode(head, node2);
53         pre->next = node1;
54         node2->next = node1->next;
55         node1->next = node2;
56     }
57     else if (node1 != node2)
58     {
59         ListNode* pre1 = findPreNode(head, node1);
60         ListNode* pre2 = findPreNode(head, node2);
61         ListNode* tmp = node1->next;
62         node1->next = node2->next;
63         node2->next = tmp;
64         pre1->next = node2;
65         pre2->next = node1;
66     }
67     return head;
68 }
69 
70 ListNode* createNode()
71 {
72     int in;
73     ListNode* head = nullptr;
74     cout << "enter list value (enter 100 to quit):";
75     cin >> in;
76     if (in == 100)
77         return head;
78     else
79     {
80         head = new ListNode(in);
81         head->next = createNode();
82     }
83     return head;
84 }
85 
86 int main()
87 {
88     ListNode* head = createNode();
89     ListNode* node1 = head->next;
90     ListNode* node2 = head->next->next->next->next;
91     printListNode(head);
92     printListNode(exchangeTwoNode(head, node1, node2));
93 
94     return 0;
95 }

View Code

18、双向链表的插入

  1 #include<iostream>
  2 
  3 using namespace std;
  4 
  5 class ListNode
  6 {
  7 public:
  8     int val;
  9     ListNode *next;
 10     ListNode *prior;
 11     ListNode(){}
 12     ListNode(int x):val(x),next(nullptr),prior(nullptr){}
 13 };
 14 
 15 ListNode* createList()
 16 {
 17     ListNode *first = new ListNode(-1);
 18     first->next = nullptr;
 19     first->prior = nullptr;
 20     ListNode* p = first;
 21     int in;
 22     while (true)
 23     {
 24         cout << "enter list value (enter 100 to quit):";
 25         cin >> in;
 26         if (in == 100)
 27             break;
 28         else
 29         {
 30             ListNode* node = new ListNode(in);
 31             p->next = node;            
 32             node->prior = p;
 33             node->next = nullptr;
 34             p = node;
 35         }
 36     }
 37     return first->next;
 38 }
 39 
 40 void printList(ListNode* head)
 41 {
 42     if (head == nullptr)
 43         return;
 44     ListNode* p = head;
 45     ListNode* last = head;
 46     while (p)
 47     {
 48         cout << p->val << " ";
 49         p = p->next;
 50     }
 51     cout << endl;
 52     while (last->next)
 53         last = last->next;
 54     while (last->prior)
 55     {
 56         cout << last->val << " ";
 57         last = last->prior;
 58     }
 59     cout << endl;
 60 }
 61 
 62 void insertNode(ListNode* head, int pos, int val)
 63 {
 64     ListNode* node = new ListNode(val);
 65     ListNode* p = head;
 66     ListNode* last = head;
 67     if (pos == 0)
 68     {
 69         node->val = head->val;
 70         head->val = val;
 71         node->next = head->next;
 72         head->next->prior = node;
 73         head->next = node;
 74         node->prior = head;
 75     }
 76     else
 77     {
 78         int index = 1;
 79         while (p&&index < pos)
 80         {
 81             ++index;
 82             p = p->next;
 83         }
 84         if (p)
 85         {
 86             node->next = p->next;
 87             p->next->prior = node;
 88             p->next = node;
 89             node->prior = p;
 90         }
 91         else
 92         {
 93             while (last->next)
 94                 last = last->next;
 95             last->next = node;
 96             node->prior = last;
 97         }
 98     }
 99 }
100 
101 int main()
102 {
103     ListNode* head = createList();
104     printList(head);
105     insertNode(head, 6, 9);
106     printList(head);
107 
108     return 0;
109 }

View Code