剑指offer面试题系列

题目：输入两个递增排序的链表，合并这两个链表并且使新链表的节点仍然是递增排序。

分析

有两种想法：一种是新创建一个链表，设置两个指针，分别指向两个链表的头部，每次都取两个指针中的最小元素的内容值，作为新的链表节点的内容。这种方法费时费力。作罢。

另一种就是在原来的两个链表上进行操作。只需要更改表的指针即可完成任务。

但是更改方式不知一种，我只想到一种非递归方式的，实现过程较为繁琐；但是经过剑指offer提醒，又实现了一种递归方式的。哎，递归，又没有想起来。明显递归的方式思路更加清晰而简洁。因为每次都是把最小的元素摘出来，让上一个结点的指针指向它，然后在剩下的部分里继续找这样的节点。

代码

非递归代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public static void MergeList(ListNode head1, ListNode head2,
			ListNode newHead) {
		// 分别指向两个表的头结点
		ListNode p1 = head1.next;
		ListNode p2 = head2.next;
		newHead.next = p1.data < p2.data ? p1 : p2; // 确定头结点
		ListNode p = new ListNode();

		for (p = head1; p1 != null && p2 != null; p = p.next) {
			if (p1.data < p2.data) {
				p.next = p1;
				p1 = p1.next;
			} else {
				p.next = p2;
				p2 = p2.next;
			}
		}

		if (p1 == null) {
			p.next = p2;
		} else {
			p.next = p1;
		}

	}

递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public static ListNode MergeRecursively(ListNode node1, ListNode node2) {
		if (node1 == null)
			return node2;
		if (node2 == null)
			return node1;
		ListNode node = new ListNode();
		if (node1.data < node2.data) {
			node = node1;
			node.next = MergeRecursively(node1.next, node2);
		} else {
			node = node2;
			node.next = MergeRecursively(node1, node2.next);
		}

		return node;
}

总结

需要注意程序的健壮性；
递归的思想还需要领悟，在你一筹莫展时，不要忘了递归这个神奇的武器。