leedcode 初级算法 链表
链接
删除链表中的节点
题目解析
请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点。传入函数的唯一参数为 要被删除的节点 。
题目解析
懒得解析了
删除链表的倒数第N个节点
题目描述
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
进阶:你能尝试使用一趟扫描实现吗?
题目解析 方法一
为头节点head建立一个前驱结点heeaad,这样就不怕只有head一个结点的情况了。先遍历一遍链表得到链表的长度,再从heeaad遍历链表,r->next,指向的是当前应该删除的结点。记住不要让r指向当前应该删除的结点,不然含需要一个r的前驱节点。
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
| class Solution { public: int getLength(ListNode *head) { int length = 0; while (head) { length++; head = head->next; } return length; } ListNode *removeNthFromEnd(ListNode *head, int n) { int length = getLength(head); if (length == 0) return NULL; n = length + 1 - n; ListNode *heeaad = new ListNode(0, head); ListNode *r = new ListNode; r = heeaad; for (int i = 1; i <= n - 1; i++) { r = r->next; } r->next = r->next->next; ListNode *ans = heeaad->next; delete heeaad; return ans; } };
|
题目解析 方法二
使用栈,向将链表中的所有数据先存起来,然后依次从前面插入。
反转链表
题目描述
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
题目解析 方法一
遍历一遍,从左到右依次设置三个指针t1 t2 t3。
每一个循环中的装填都是 t2已经设置好指向,t2需要改变指向到t1,t3指向下一轮循环需要改变的结点。
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
| #include <iostream> #include <vector> #include <algorithm> #include <unordered_set> #include <unordered_map> #include <deque> #include <utility> #include <map> #include <stack> using namespace std;
struct ListNode { int val; struct ListNode *next; };
struct ListNode *reverseList(struct ListNode *head) { if (head == NULL || head->next == NULL) { return head; } ListNode *t1 = NULL, *t2 = NULL, *t3 = NULL; t1 = head; t2 = head->next; t1->next = NULL; do { t3 = t2->next; t2->next = t1; if (t3 == NULL) { return t2; } t1 = t2; t2 = t3; t3 = t3->next; } while (1); return 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
| #include <iostream> #include <vector> #include <algorithm> #include <unordered_set> #include <unordered_map> #include <deque> #include <utility> #include <map> #include <stack> using namespace std;
struct ListNode { int val; struct ListNode *next; };
struct ListNode *reverseList(struct ListNode *head) { if (head == NULL || head->next == NULL) { return head; } struct ListNode *res = reverseList(head->next); head->next->next = head; head->next = NULL; return res; }
|
合并有序链表
题目描述
合并两个递增链表
题目解析 方法一
迭代,先设立一个伪头节点,比较l1 l2的大小,将游标指向小的,并后移对应链表l1或l2,直到一个为空
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
| #include <iostream> #include <vector> #include <algorithm> #include <unordered_set> #include <unordered_map> #include <deque> #include <utility> #include <map> #include <stack> #include <malloc.h> #include <random> #include <time.h> using namespace std;
struct ListNode { int val; struct ListNode *next; };
struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2) { struct ListNode *res = (struct ListNode *)malloc(sizeof(struct ListNode)); res->next = NULL; struct ListNode *t = res; while (1) { if (l1 == NULL) { t->next = l2; return res->next; } if (l2 == NULL) { t->next = l1; return res->next; } if (l1->val <= l2->val) { t->next = l1; l1 = l1->next; t = t->next; } else { t->next = l2; l2 = l2->next; t = t->next; } } }
|
题目解析 方法二
递归
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
| #include <iostream> #include <vector> #include <algorithm> #include <unordered_set> #include <unordered_map> #include <deque> #include <utility> #include <map> #include <stack> #include <malloc.h> #include <random> #include <time.h> using namespace std;
struct ListNode { int val; struct ListNode *next; };
struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2) { if (l1 == NULL) { return l2; } if (l2 == NULL) { return l1; } if (l1->val <= l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l2->next, l1); return l2; } }
|
回文链表
题目描述
判断一个链表是否是回文链表
题目解析 方法一
将链表从中间分为两部分,将其中一部分进行反转,顺序比较是否相等。
这个解法和力扣官方解法的快慢指针相同。
在并发环境中这个解法需要进行链表访问的锁定,因为在访问中会进行更改链表。
在程序的最后还需要将链表复原。
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
| #include <iostream> #include <vector> #include <algorithm> #include <unordered_set> #include <unordered_map> #include <deque> #include <utility> #include <map> #include <stack> #include <malloc.h> #include <random> #include <time.h> using namespace std;
struct ListNode { int val; struct ListNode *next; };
struct ListNode *reverseList(struct ListNode *head) { if (head == NULL || head->next == NULL) { return head; } struct ListNode *res = reverseList(head->next); head->next->next = head; head->next = NULL; return res; }
bool isPalindrome(struct ListNode *head) { int count = 0; struct ListNode *h = head; while (h) { count++; h = h->next; } count /= 2; struct ListNode *l1 = head; struct ListNode *l2 = head; while (count > 0) { count--; l2 = l2->next; } l2 = reverseList(l2); while (l1 && l2) { if (l1->val != l2->val) { return false; } l1 = l1->next; l2 = l2->next; } return true; }
|
题目解析 方法二
复制到数组里面,这个方法太幼稚了。略。
题目解析 方法三
递归,使用后序遍历的递归。由于递归天然具有从后向前的特性,所以用来从后向前遍历是再好不过的。在函数外设置一个变量用来指示从前向后遍历进行并比较的结点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| struct ListNode *now = NULL;
bool check(struct ListNode *head) { if (head) { if (!check(head->next)) return false; if (head->val != now->val) { return false; } now = now->next; } return true; }
bool isPalindrome(struct ListNode *head) { now = head; return check(head); }
|
环形链表
题目描述
判断一个链表是否有环,即遍历永远不会结束。
题目解析 方法一
这是一个投机的方法。根据是系统分配内存是从小开始分配。不可以在真实环境中使用。
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| bool hasCycle(struct ListNode *head) { if (head == NULL || head->next == NULL) { return false; } while (head->next) { if (head->next <= head) return true; head = head->next; } return false; }
|
题目解析 方法二
使用哈希表记录每一次遍历到的结点地址。遍历时判断是否已经遍历过。
1 2 3 4 5 6 7 8 9 10 11 12
| bool hasCycle(struct ListNode *head) { unordered_set<struct ListNode *> set; while(head) { if(set.count(head)) return true; set.insert(head); head=head->next; } return false; }
|
题目解析 方法三
快慢指针
使用两个指针 兔子和乌龟 兔子一次走两步,乌龟一次走一步,直到结尾。若相遇说明有环。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| bool hasCycle(struct ListNode *head) { if (head == NULL || head->next == NULL) return false; struct ListNode *tu, *gui; gui = head; tu = head->next; while (tu && gui) { if (tu == gui) return true; gui = gui->next; tu = tu->next; if (tu == NULL) return false; else tu = tu->next; } return false; }
|