08-链表

学习链表几个方法

1. 学会画图，通过图像来比较方便地理解内容
2. 可以使用虚拟的头结点，这样可以减少一部分边界情况
3. 可以使用临时节点，这样可以防止链表断开，减少思考步骤

题目

LC2. 两数相加

思路：

1. 观察题目，发现这个题目不是正序的，而是逆序（从小到大）的，因此不需要翻转列表
2. 遍历列表，从末尾开始，用 t 来存储两个链表相加的值，然后创建一个新的节点，把个位数的值给加进去。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
	ListNode head = new ListNode(-1), cur = head;
	int t = 0;
	while (l1 != null || l2 != null || t != 0) {
		if (l1 != null) {
			t += l1.val;
			l1 = l1.next;
		}
		if (l2 != null) {
			t += l2.val;
			l2 = l2.next;
		}

		cur.next = new ListNode(t % 10);
		cur = cur.next;
		t /= 10;
	}

	return head.next;
}

LC24. 两两交换链表中的节点

这个就要用到我之前说的内容了：

1. 创建虚拟头结点
2. 画图来思考，尤其是遇到空指针的时候
3. 创建临时的节点

public ListNode swapPairs(ListNode l) {
	if (l == null || l.next == null) return l;
	ListNode head = new ListNode(-1);
	head.next = l;

	// 定义四个指针
	ListNode c1 = head, c2 = c1.next, c3 = c2.next, c4 = c3.next;

	while (true) {
		c1.next = c3;
		c3.next = c2;
		c2.next = c4;
		if (c4 == null || c4.next == null) break;
		c1 = c2;
		c2 = c1.next;
		c3 = c2.next;
		c4 = c3.next;
	}

	return head.next;
}

LC143. 重排链表

这个题目是一个综合题，它涉及了三个简单题目的思路

思路：

1. 找到链表的中点
2. 然后把后面的列表经行翻转
3. 合并两个列表（非有序）

public void reorderList(ListNode head) {
	if (head == null || head.next == null) return;

	// 1. 找到中间节点
	ListNode slow = head, fast = head.next; // 把 slow/fast 放在 head 上面就已经算作一步了
	while (fast != null && fast.next != null) {
		slow = slow.next;
		fast = fast.next.next;
	}

	ListNode tmp = slow.next;
	slow.next = null;
	slow = tmp;

	// 2. 翻转后半部分列表
	ListNode lastNodeHead = new ListNode(-1), lastNodeHeadNext = null, slowNext = null;
	while (slow != null) {
		lastNodeHeadNext = lastNodeHead.next;
		slowNext = slow.next;
		lastNodeHead.next = slow;
		slow.next = lastNodeHeadNext;
		slow = slowNext;
	}
	// print(head);
	// print(lastNodeHead.next);

	ListNode cur1 = head, cur2 = lastNodeHead.next;
	// 3. 合并数组
	ListNode tmpHead = new ListNode(-1), cur = tmpHead;
	while (cur1 != null && cur2 != null) {
		cur.next = cur1;
		cur = cur.next;
		cur1 = cur1.next;
		cur.next = cur2;
		cur = cur.next;
		cur2 = cur2.next;
	}
	// 考虑个数奇数的情况
	if (cur1 != null) {
		cur.next = cur1;
		cur1.next = null;
	}

	// print(tmpHead);
}

private void print(ListNode node) {
	while (node != null) {
		System.out.print(node.val + " -> ");
		node = node.next;
	}
	System.out.println("null");
}

LC23. 合并 K 个升序链表

这个题目有两个解法，一个解法的通过优先级队列来求解，另一个是通过递归的方式求解。

优先级队列

思路：

1. 创建一个优先级队列，把各个列表中的头结点放入优先级队列中
2. 每次获取到堆顶元素，然后堆顶元素直接插入就可以了，如果有下一个节点，那还需要把堆顶元素的下一个节点放回去

这个是和之前的思路一样，只不过是从两个队列比较大小转变为 k 个队列比较大小。

总共遍历个数为 $n\times k$, 每次比较的个数为 $\log k$ ，因此它是时间复杂度为 $nk\times \log k$

public ListNode mergeKLists(ListNode[] lists) {
	// 解法1 使用优先级队列 
	PriorityQueue<ListNode> queue = new PriorityQueue<>((o1, o2) -> {
		// 需要传入比较，不然会出错
		return o1.val - o2.val;
	});
	int n = lists.length;
	
	// 初始化, 先把最上面的插入
	for (int i = 0; i < n; i++) {
		if (lists[i] != null) queue.offer(lists[i]); // 考虑为空的情况，如果为空 那么就不插入，不然会有空指针的异常
	}
	
	ListNode tmpHead = new ListNode(-1), cur = tmpHead;
	while (!queue.isEmpty()) {
		ListNode tmp = queue.poll(); // 获取到堆顶元素
		if (tmp.next != null) queue.offer(tmp.next);
		cur.next = tmp;
		cur = cur.next;
	}

	return tmpHead.next;
}

递归

思路：

1. 主线流程：由于是有序列表，因此可以采用类似归并排序，先排左边那一部分，然后再排右边那一部分，最后再合并一下
2. 终止条件：当到达最下面的时候，既只有一个元素的时候就要停止

public ListNode mergeKLists(ListNode[] lists) {
	// 使用递归来整理
	return merge(0, lists.length - 1, lists);
}

private ListNode merge(int left, int right, ListNode[] lists) {
	if (left == right) return lists[left];
	if (left > right) return null;

	int mid = (right - left) / 2 + left;
	ListNode leftHead = merge(left, mid, lists);
	ListNode rightHead = merge(mid + 1, right, lists);

	// 合并
	ListNode tmpHead = new ListNode(-1), prev = tmpHead, cur1 = leftHead, cur2 = rightHead;
	while (cur1 != null && cur2 != null) {
		if (cur1.val < cur2.val) {
			prev.next = cur1;
			cur1 = cur1.next;
		} else {
			prev.next = cur2;
			cur2 = cur2.next;
		}
		prev = prev.next;
	}
	prev.next = cur1 != null ? cur1 : cur2; // 由于是链表，所以只需要改一个节点就可以了
	return tmpHead.next;
}

LC25. K 个一组翻转链表

思路：

1. 先遍历一次链表，计算出它的长度，然后计算出需要翻转的区间的个数 count
2. 执行两次循环，外面一层表示翻转区间的个数，内部表示同一个区间内翻转的详细逻辑
3. 最后只要把尾巴加上就可以了

public ListNode reverseKGroup(ListNode head, int k) {
	// 计算出长度
	int n = 0;
	ListNode cur = head;
	while (cur != null) {
		cur = cur.next;
		n++;
	}

	// 两层循环
	int count = n / k; // 执行次数
	ListNode tmpHead = new ListNode(-1), prev = tmpHead;
	cur = head;
	for (int i = 0; i < count; i++) {
		ListNode last = cur; // 记录最后的节点的位置            
		for (int j = 0; j < k; j++) {
			// 头插
			ListNode next = cur.next;
			cur.next = prev.next;
			prev.next = cur;
			cur = next;
		}
		// 把 prev 迁移到最后的一个节点上面
		prev = last;
	}

	// 把最后的末尾接上
	prev.next = cur;
	
	return tmpHead.next;
}