Leetcode|Linked List Problem Sets

概述

本文为 Labuladong 算法小抄 的第一章节，手把手刷链表算法的部分，个人刷题帖子。

每七天一更新，一天一题，第七天把前六天的题目重新回顾一遍。

双指针技巧

合并两个有序链表

题目

思路分析

很简单的一个思路，本题的具体实现其实和 归并排序 中的 merge 部分一脉相承，是一个很经典的双指针算法。

两个指针指向两个升序链表，每一次我们都比较哪一个小，维护一个新的链表，把每一次指针指向的最小的那个元素加入到新维护的链表中即可。

最终记得和归并排序的 merge 处理一样，我们还需要进行扫尾操作

代码实现

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
	ListNode dummy = new ListNode(0, null);
	ListNode c1 = list1;
	ListNode c2 = list2;
	ListNode res = dummy;
	while (c1 != null && c2 != null) {
		if (c1.val >= c2.val) {
			dummy.next = c2;
			c2 = c2.next;
		}
		else {
			dummy.next = c1;
			c1 = c1.next;
		}
		dummy = dummy.next;
	}
	if (c1 == null) {
		dummy.next = c2;
	}
	if (c2 == null) {
		dummy.next = c1;
	}
	return res.next;
}