题目

合并两个有序的升序链表

实现

可以使用迭代法和递归法两种方法实现

Python实现

class Solution:
	def mergeTwoSortedList(self, l1, l2):
		res = ListNode()
		cur = res
		# python中不需要加while循环后的括号
		while l1 and l2:
			if l1.val <= l2.val:
				cur.next = l1
				l1 = l1.next
			else:
				cur.next = l2
				l2 = l2.next
			cur = cur.next
		# 注意是 cur.next = l1 or l2，而不是 cur = l1 or l2
		cur.next = l1 or l2
		return res.next

class ListNode:
	# python中的构造方法是 __init__, 而不是 __ini__
	def __init__(self, val=0, next=None):
		self.val = val
		self.next = next

def create_linked_list(varList):
	res = ListNode()
	cur = res
	for i in varList:
		now = ListNode()
		now.val = i
		cur.next = now
		# 注意这里要加上 cur = cur.next,实现链表指针的移动
		cur = cur.next
	return res.next

def print_linked_list(varListNode):
	string = ""
	if not varListNode:
		return
	if not varListNode.next:
		# python中的打印是 print()
		print(varListNode.val)
		return

	while varListNode:
		string += f"{varListNode.val}"
		if varListNode.next:
			string += "->"
		varListNode = varListNode.next
	print(string)


l1 = create_linked_list([1,2,3])
l2 = create_linked_list([4,5,6])
solution = Solution()
l3 = solution.mergeTwoSortedList(l1, l2)
print_linked_list(l3)

Java实现

import java.util.Arrays;
import java.util.List;
class Solution {
	public static ListNode mergeTwoSortedListNode(ListNode l1, ListNode l2){
		//创建一个哨兵节点（dummy node），作为结果链表的头节点前一个节点
		ListNode res = new ListNode();
		//cur指向当前结果链表的最后一个节点，初始时就是哨兵节点
		ListNode cur = res;
		while(l1 != null && l2 != null){
			if(l1.val <= l2.val){
				cur.next = l1;
				l1 = l1.next;
			} else {
				cur.next = l2;
				l2 = l2.next;
			}
			cur = cur.next;
		}
         //将剩余的非空链表接在结果链表后面
		cur.next = l1 != null ? l1 : l2;
		return res.next;
	}



	public static ListNode createListNode(List<Integer> list) {
		ListNode dummy = new ListNode();
		ListNode cur = dummy;
		for (Integer i : list) {
			cur.next = new ListNode(i);
			cur = cur.next;
		}
		return dummy.next;
	}

	public static void printListNode(ListNode listNode){
		StringBuilder sb = new StringBuilder();
		while(listNode != null){
			sb.append(listNode.val);
			if(listNode.next != null) {
				sb.append("->");
			}
			listNode = listNode.next;
		}
		System.out.println(sb.toString());
	}

	public static void main(String[] args){
		Integer[] l1Array = {1,2,3};
		ListNode l1 = createListNode(Arrays.asList(l1Array));
		Integer[] l2Array = {4,5,6};
		ListNode l2 = createListNode(Arrays.asList(l2Array));
		ListNode l3 = mergeTwoSortedListNode(l1, l2);
		printListNode(l3);

	}
}

class ListNode {
	public int val;
	public ListNode next;
	ListNode(int val, ListNode next){
		this.val = val;
		this.next = next;
	}
	ListNode(int val){
		this.val = val;			
	}
	ListNode(){

	}
}

代码解释

现实生活类比
想象你在组织一场拔河比赛：

res 是起点锚点（固定不动）
cur 是传递绳索的人（从起点走到终点）
当你完成绳索连接后：
返回 cur：只能看到最后一个人的位置
返回 res.next：可以看到第一个队员开始的所有队员

res和cur的关系：
res是固定锚点：永远不会移动，其.next属性永远指向合并后链表的​​头部​​
cur是工作指针：负责遍历和连接节点，始终指向当前链表的​​尾部​​
整个过程：res提供访问入口，cur执行连接操作

关键点总结：
​​哨兵节点(dummy node)​​：简化边界处理，避免空指针异常
​​双指针工作方式​​：cur负责构建链表，原链表指针(l1/l2)负责遍历
​​剩余节点处理​​：当任一链表遍历完后，直接连接另一个链表的剩余部分
​​返回值​​：哨兵节点的next才是真正合并后的链表头节点