《剑指offer》面试题17 合并两个排序的链表 Java版

我的方法：新初始化一个链表头，比较两个链表当前节点的大小，然后连接到该链表中。遍历两个链表直到null为止。

	public ListNode merge(ListNode first, ListNode second){

		//注意这个细节

      	ListNode head = new ListNode(0);

		ListNode index = head;

		while(first != null && second != null){

			if(first.val < second.val){

				index.next = first;

				first = first.next;

			}else{

				index.next = second;

				second = second.next;

			}

			index = index.next;

		}

		if(first != null)index.next = first;

		else index.next = second;

		return head.next;

	}

书中方法：我们每一次都是找两个链表值中较小的作为结果节点，它的下一个节点依旧会重复一样的过程，这是典型的递归过程，可以得到以下的递归方法。先处理后递归，最后的返回值是头节点，每次递归的返回值是较小的节点。

	public ListNode merge2(ListNode first, ListNode second){

		if(first == null)return second;

		if(second == null)return first;

		ListNode nowHead = null;

		if(first.val < second.val){

			nowHead = first;

			nowHead.next = merge2(first.next, second);

		}else{

			nowHead = second;

			nowHead.next = merge2(first, second.next);

		}

		return nowHead;

	}

巴特西

《剑指offer》面试题17 合并两个排序的链表 Java版

最新文章

热门文章