算法——链表总结及扩展题

目录

 
扩展题

　　下图中打勾的题目为前两个专题中已经做过的，接下来我们就来联系一下剩余的题目。

• 回文链表234. 回文链表 - 力扣（LeetCode）
  
• 21. 合并两个有序链表 - 力扣（LeetCode）
  
• 2. 两数相加 - 力扣（LeetCode）
  
• 25. K 个一组翻转链表 - 力扣（LeetCode）
  
• 138. 随机链表的复制 - 力扣（LeetCode）
  
• 148. 排序链表 - 力扣（LeetCode）
  
• 23. 合并 K 个升序链表 - 力扣（LeetCode）
  
• 146. LRU 缓存 - 力扣（LeetCode）
  

 
一、回文链表

 　　思路：我刚开始的做法是把整个节点入栈，但这样是不对的！！应该只用把节点的值入栈即可。回文：倒着和正着是一样的，这就可以先把所有节点入栈（后进先出），然后第二次遍历逐个比较栈顶元素（出栈的顺序跟本身顺序相反）
　　代码：

1. /**
2. * Definition for singly-linked list.
3. * public class ListNode {
4. *     int val;
5. *     ListNode next;
6. *     ListNode() {}
7. *     ListNode(int val) { this.val = val; }
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
9. * }
10. */
11. class Solution {
12.     public boolean isPalindrome(ListNode head) {
13.         //借助栈来做
14.         Deque<Integer> stack = new LinkedList<>();
15.         ListNode cur = head;
16.         //第一次遍历
17.         while(cur != null){
18.             stack.push(cur.val);
19.             cur = cur.next;
20.         }
21.         //第二次遍历
22.         cur = head;
23.         while(cur != null){
24.             if(stack.pop() != cur.val){
25.                 return false;           //只要有一个不一样，就不是回文
26.             }
27.             cur = cur.next;
28.         }
29.         return stack.isEmpty();
30.     }
31. }
32. //时间复杂度：O(N)
33. //空间复杂度：O(N)

复制代码

 
二、合并两个有序链表

[code]class Solution {    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {        ListNode dummyHead = new ListNode();        ListNode p1 = list1;        ListNode p2 = list2;        ListNode cur = dummyHead;        while(p1!=null && p2!=null){            if(p1.val = k; n -= k){            for(int i=0; i