当前位置:  首页>> 技术小册>> 数据结构与算法(下)

题目描述

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

解法

解法一

同时遍历两链表进行 merge

  1. /**
  2. * @author bingo
  3. * @since 2018/11/22
  4. */
  5. /*
  6. public class ListNode {
  7. int val;
  8. ListNode next = null;
  9. ListNode(int val) {
  10. this.val = val;
  11. }
  12. }*/
  13. public class Solution {
  14. /**
  15. * 合并两个排序链表
  16. * @param list1 链表1
  17. * @param list2 链表2
  18. * @return 合并后的单调不递减链表
  19. */
  20. public ListNode Merge(ListNode list1, ListNode list2) {
  21. if (list1 == null) {
  22. return list2;
  23. }
  24. if (list2 == null) {
  25. return list1;
  26. }
  27. ListNode dummy = new ListNode(-1);
  28. ListNode cur = dummy;
  29. ListNode p1 = list1;
  30. ListNode p2 = list2;
  31. while (p1 != null && p2 != null) {
  32. if (p1.val < p2.val) {
  33. ListNode t = p1.next;
  34. cur.next = p1;
  35. p1.next = null;
  36. p1 = t;
  37. } else {
  38. ListNode t = p2.next;
  39. cur.next = p2;
  40. p2.next = null;
  41. p2 = t;
  42. }
  43. cur = cur.next;
  44. }
  45. cur.next = p1 == null ? p2 : p1;
  46. return dummy.next;
  47. }
  48. }

解法二:递归

  1. /**
  2. * @author bingo
  3. * @since 2018/11/22
  4. */
  5. /*
  6. public class ListNode {
  7. int val;
  8. ListNode next = null;
  9. ListNode(int val) {
  10. this.val = val;
  11. }
  12. }*/
  13. public class Solution {
  14. /**
  15. * 合并两个排序链表
  16. * @param list1 链表1
  17. * @param list2 链表2
  18. * @return 合并后的单调不递减链表
  19. */
  20. public ListNode Merge(ListNode list1, ListNode list2) {
  21. if (list1 == null) {
  22. return list2;
  23. }
  24. if (list2 == null) {
  25. return list1;
  26. }
  27. if (list1.val < list2.val) {
  28. list1.next = Merge(list1.next, list2);
  29. return list1;
  30. }
  31. list2.next = Merge(list1, list2.next);
  32. return list2;
  33. }
  34. }

测试用例

  1. 功能测试(输入的两个链表有多个节点;节点的值互不相同或者存在值相等的多个节点);
  2. 特殊输入测试(两个链表的一个或者两个头节点为空指针;两个链表中只有一个节点)。

该分类下的相关小册推荐: