[随缘一题]合并两个排序链表

数据结构和算法►链表 , , , , 评论

来源:

lintcode-165. 合并两个排序链表

描述

将两个排序链表合并为一个新的排序链表

样例

1
给出 1->3->8->11->15->null，2->null， 返回 1->2->3->8->11->15->null。

解题思路

这道题的重点在于链表是已排序的.

那么其实可以比较两个链表当前节点的值,哪个值小,就把它连接在新链表的后面,并将这个链表的当前指针后移一位.知道某一个链表为空,将另一个链表的所有值链接在后面即可.

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  //由于不知道两个链表哪个头结点大,所以自定义一个头结点
  ListNode dummy = new ListNode(-1), cur = dummy;
  //当两个链表都不为空
  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 dummy.next;
}

完。




ChangeLog

2018-01-05 完成

以上皆为个人所思所得，如有错误欢迎评论区指正。

欢迎转载，烦请署名并保留原文链接。

联系邮箱：huyanshi2580@gmail.com

更多学习笔记见个人博客——>呼延十

呼延十Developer

个人简介。