算法——链表总结及扩展题
目录扩展题
下图中打勾的题目为前两个专题中已经做过的，接下来我们就来联系一下剩余的题目。
[*]回文链表234. 回文链表 - 力扣（LeetCode）
[*]21. 合并两个有序链表 - 力扣（LeetCode）
[*]2. 两数相加 - 力扣（LeetCode）
[*]25. K 个一组翻转链表 - 力扣（LeetCode）
[*]138. 随机链表的复制 - 力扣（LeetCode）
[*]148. 排序链表 - 力扣（LeetCode）
[*]23. 合并 K 个升序链表 - 力扣（LeetCode）
[*]146. LRU 缓存 - 力扣（LeetCode）
一、回文链表
思路：我刚开始的做法是把整个节点入栈，但这样是不对的！！应该只用把节点的值入栈即可。回文：倒着和正着是一样的，这就可以先把所有节点入栈（后进先出），然后第二次遍历逐个比较栈顶元素（出栈的顺序跟本身顺序相反）
代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
//借助栈来做
Deque<Integer> stack = new LinkedList<>();
ListNode cur = head;
//第一次遍历
while(cur != null){
stack.push(cur.val);
cur = cur.next;
}
//第二次遍历
cur = head;
while(cur != null){
if(stack.pop() != cur.val){
return false; //只要有一个不一样，就不是回文
}
cur = cur.next;
}
return stack.isEmpty();
}
}
//时间复杂度：O(N)
//空间复杂度：O(N)
二、合并两个有序链表
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
页:
[1]