设计平台市场分析_沙坪坝最新消息今天_搜索引擎地址_优化网站首页

链表算法题技巧

1. 画图!
2. 引入虚拟"头"结点
   便于处理边界情况
   方便我们对链表操作
3. 不要吝啬空间, 大量去定义变量

链表中的常见操作

1. 创建一个新的节点
2. 尾插
3. 头插(逆序链表)

一. 两数相加

两数相加

/*** 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 ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode cur1 = l1;ListNode cur2 = l2;ListNode newHead = new ListNode(0);//创建一个虚拟头结点, 记录结果ListNode tail = newHead;//记录每次尾插的位置int t = 0;  //将想家的结果放在t中while(cur1 != null || cur2 != null || t != 0){//有进位也要继续算if(cur1 != null){t += cur1.val;cur1 = cur1.next;}if(cur2 != null){t += cur2.val;cur2 = cur2.next;}tail.next = new ListNode(t % 10);//取个位tail = tail.next;t /= 10;//取进位, 加到下一次的结果中}return newHead.next;}
}

二. 两两交换列表中的结点

两两交换列表中的结点

class Solution {public ListNode swapPairs(ListNode head) {if(head == null || head.next == null){return head;}ListNode newHead = new ListNode(0);newHead.next = head;ListNode prev = newHead;ListNode cur1 = head;ListNode cur2 = head.next;ListNode tail = cur2.next;while(cur1 != null && cur2 != null){prev.next = cur2;cur2.next = cur1;cur1.next = tail;prev = cur1;cur1 = tail;if(cur1 != null) cur2 = cur1.next;if(cur2 != null) tail = cur2.next;}return newHead.next;}
}

三. 重排链表

重排链表

class Solution {public void reorderList(ListNode head) {// 1. 找到链表的中间结点, 将链表一分为二ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}// 2. 将后半链表逆序, 头插法ListNode cur = slow.next;slow.next = null;// 将前后链表分离ListNode head2 = new ListNode(0);while (cur != null) {ListNode next = cur.next;cur.next = head2.next;head2.next = cur;cur = next;}// 3. 将两个链表合并ListNode cur1 = head;ListNode cur2 = head2.next;ListNode ret = new ListNode(0);ListNode prev = ret;while (cur1 != null) {prev.next = cur1;cur1 = cur1.next;prev = prev.next;if (cur2 != null) {prev.next = cur2;cur2 = cur2.next;prev = prev.next;}}}
}

四. 合并k个升序链表

合并k个升序链表

class Solution {public ListNode mergeKLists(ListNode[] lists) {//1. 创建一个小根堆PriorityQueue<ListNode> heap = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);//2. 把所有的头结点放在小根堆中for(ListNode head : lists){if(head != null){heap.offer(head);}}//3. 合并链表ListNode ret = new ListNode(0);ListNode prev = ret;while(!heap.isEmpty()){ListNode t = heap.poll();prev.next = t;prev = prev.next;if(t.next != null){heap.offer(t.next);}}return ret.next;}
}