当前位置:   article > 正文

算法--合并链表_new listnode(-1);

new listnode(-1);

1、合并两个有序链表

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。

  1. class Solution {
  2. public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  3. //定义一个头结点
  4. ListNode prehead = new ListNode(-1);
  5. //当前节点
  6. ListNode prev = prehead;
  7. while (l1 != null && l2 != null) {
  8. //当前节点指向值比较小的节点
  9. if (l1.val <= l2.val) {
  10. prev.next = l1;
  11. l1 = l1.next;
  12. } else {
  13. prev.next = l2;
  14. l2 = l2.next;
  15. }
  16. prev = prev.next;
  17. }
  18. // 合并后 l1 和 l2 最多只有一个还未被合并完,我们直接将链表末尾指向未合并完的链表即可
  19. prev.next = l1 == null ? l2 : l1;
  20. return prehead.next;
  21. }
  22. }

2、合并两个链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

  1. //使用归并排序实现链表的升序
  2. //时间复杂度 O(nlogn) 空间复杂度O(n)
  3. class Solution {
  4. public ListNode sortList(ListNode head) {
  5. return sortList(head, null);
  6. }
  7. public ListNode sortList(ListNode head, ListNode tail) {
  8. if (head == null) {
  9. return head;
  10. }
  11. if (head.next == tail) {
  12. head.next = null;
  13. return head;
  14. }
  15. //使用快慢指针,慢指针一次移动一个节点,快指针一次移动两个结点
  16. //最终 慢指针停在中点,快指针停在尾结点
  17. ListNode slow = head, fast = head;
  18. while (fast != tail) {
  19. slow = slow.next;
  20. fast = fast.next;
  21. if (fast != tail) {
  22. fast = fast.next;
  23. }
  24. }
  25. ListNode mid = slow;
  26. ListNode list1 = sortList(head, mid);
  27. ListNode list2 = sortList(mid, tail);
  28. ListNode sorted = merge(list1, list2);
  29. return sorted;
  30. }
  31. //合并两个有序数组
  32. public ListNode merge(ListNode head1, ListNode head2) {
  33. ListNode dummyHead = new ListNode(0);
  34. ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
  35. while (temp1 != null && temp2 != null) {
  36. if (temp1.val <= temp2.val) {
  37. temp.next = temp1;
  38. temp1 = temp1.next;
  39. } else {
  40. temp.next = temp2;
  41. temp2 = temp2.next;
  42. }
  43. temp = temp.next;
  44. }
  45. if (temp1 != null) {
  46. temp.next = temp1;
  47. } else if (temp2 != null) {
  48. temp.next = temp2;
  49. }
  50. return dummyHead.next;
  51. }
  52. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/笔触狂放9/article/detail/893356
推荐阅读
相关标签
  

闽ICP备14008679号