← 返回目录

13 指针三剑客之一:链表

第 53 / 68 卷日期:

13

hh

h

13.1

LeetCode

struct ListNode { int val;

ListNode *next;

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

(dummy node)

dummydummy->next LeetCode

13.2

206. Reverse Linked List (Easy)

Input: 1->2->3->4->5->nullptr Output: 5->4->3->2->1->nullptr

ListNode* reverseList(ListNode* head, ListNode* prev=nullptr) { if (!head) {

return prev;

} ListNode* next = head->next;

head->next = prev;

return reverseList(next, head);

}

ListNode* reverseList(ListNode* head) { ListNode *prev = nullptr, *next;

while (head) { next = head->next;

head->next = prev;

prev = head;

head = next;

} return prev;

}

21. Merge Two Sorted Lists (Easy)

Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l2) {

return l1;

if (!l1) { return l2;

if (l1->val > l2->val) {

return l2;

} l1->next = mergeTwoLists(l1->next, l2);

return l1;

}

ListNode* mergeTwoLists(ListNode *l1, ListNode *l2) { ListNode *dummy = new ListNode(0), *node = dummy;

while (l1 && l2) { if (l1->val <= l2->val) {

node->next = l1;

l1 = l1->next;

} else { node->next = l2;

l2 = l2->next;

} node = node->next;

} node->next = l1? l1: l2;

return dummy->next;

}

24. Swap Nodes in Pairs (Medium)

Input: 1->2->3->4 Output: 2->1->4->3

ListNode* swapPairs(ListNode* head) { ListNode *p = head, *s;

if (p && p->next) { s = p->next;

p->next = s->next;

s->next = p;

head = s;

while (p->next && p->next->next) { s = p->next->next;

p->next->next = s->next;

s->next = p->next;

全站分卷索引 · 68 卷
  1. 11 题目分类
  2. 22 最易懂的贪心算法
  3. 32.3 区间问题
  4. 42.4 练习
  5. 53 玩转双指针
  6. 63.2 Two Sum
  7. 73.4 快慢指针
  8. 83.5 滑动窗口
  9. 93.6 练习
  10. 104 居合斩!二分查找
  11. 114.3 查找区间
  12. 124.4 旋转数组查找数字
  13. 134.5 练习
  14. 145 千奇百怪的排序算法
  15. 155.2 快速选择
  16. 165.3 桶排序
  17. 175.4 练习
  18. 186 一切皆可搜索
  19. 196.3 回溯法
  20. 206.4 广度优先搜索
  21. 216.5 练习
  22. 227 深入浅出动态规划
  23. 237.3 基本动态规划:二维
  24. 247.4 分割类型题
  25. 257.5 子序列问题
  26. 267.6 背包问题
  27. 277.7 字符串编辑
  28. 287.8 股票交易
  29. 297.9 练习
  30. 308 化繁为简的分治法
  31. 318.3 练习
  32. 329 巧解数学问题
  33. 339.4 数字处理
  34. 349.5 随机与取样
  35. 359.6 练习
  36. 3610 神奇的位运算
  37. 3710.3 二进制特性
  38. 3810.4 练习
  39. 3911 妙用数据结构
  40. 4011.2 数组
  41. 4111.3 栈和队列
  42. 4211.4 单调栈
  43. 4311.5 优先队列
  44. 4411.6 双端队列
  45. 4511.7 哈希表
  46. 4611.8 多重集合和映射
  47. 4711.9 前缀和与积分图
  48. 4811.10 练习
  49. 4912 令人头大的字符串
  50. 5012.3 字符串理解
  51. 5112.4 字符串匹配
  52. 5212.5 练习
  53. 5313 指针三剑客之一:链表
  54. 5413.3 其它链表技巧
  55. 5513.4 练习
  56. 5614 指针三剑客之二:树
  57. 5714.3 层次遍历
  58. 5814.4 前中后序遍历
  59. 5914.5 二叉查找树
  60. 6014.6 字典树
  61. 6114.7 练习
  62. 6215 指针三剑客之三:图
  63. 6315.3 拓扑排序
  64. 6415.4 练习
  65. 6516 更加复杂的数据结构
  66. 6616.3 复合数据结构
  67. 6716.4 练习
  68. 6817 后记