当前位置:   article > 正文

相交链表Java

相交链表java

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 nu11。

以下有两种解决方法:

  • 一种是用Map,利用其key值唯一的方法去判断(也可以使用set,set在add时,已存在的元素会返回false,不存在的返回true),但是此种方法会导致额外的空间消耗;
  • 另外一种是利用双指针,获取两个链表中的长度,将最长的起始部位和最短的起始部分相等,一起遍历.
  1. static class ListNode{
  2. private int val;
  3. private ListNode node;
  4. public ListNode(int val, ListNode node) {
  5. this.val = val;
  6. this.node = node;
  7. }
  8. @Override
  9. public String toString() {
  10. return "ListNode{" +
  11. "val=" + val +
  12. ", node=" + node +
  13. '}';
  14. }
  15. }
  16. public static void main(String[] args) {
  17. ListNode node5 = new ListNode(5, null);
  18. ListNode node4 = new ListNode(4, node5);
  19. ListNode node3 = new ListNode(3, node4);
  20. ListNode node2 = new ListNode(2, node3);
  21. ListNode node1 = new ListNode(1, node2);
  22. ListNode head3 = new ListNode(3, node3);
  23. ListNode head2 = new ListNode(2, head3);
  24. ListNode head1 = new ListNode(1, head2);
  25. System.out.println("相交链表元素为:" + getIntersectionNode(head1, node1));
  26. System.out.println("相交链表元素为:" + getIntersectionNode2(head1, node1));
  27. }
  28. //相交链表
  29. private static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  30. if (headA == null || headB == null) {
  31. return null;
  32. }
  33. int a = 0, b = 0, c = 0;
  34. ListNode nodea = headA, nodeb = headB;
  35. while (nodea != null) {
  36. a++;
  37. nodea = nodea.node;
  38. }
  39. while (nodeb != null) {
  40. b++;
  41. nodeb = nodeb.node;
  42. }
  43. nodea = headA;
  44. nodeb = headB;
  45. if (a < b) {
  46. c = b - a;
  47. for (int i = 0; i < c; i++) {
  48. nodeb = nodeb.node;
  49. }
  50. } else {
  51. c = a - b;
  52. for (int i = 0; i < c; i++) {
  53. nodea = nodea.node;
  54. }
  55. }
  56. while (nodea != null && nodeb != null) {
  57. if (nodea == nodeb)
  58. return nodea;
  59. nodea = nodea.node;
  60. nodeb = nodeb.node;
  61. }
  62. return null;
  63. }
  64. private static ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
  65. Map<ListNode, Integer> map = new HashMap<>();
  66. while (headA != null) {
  67. map.put(headA, headA.val);
  68. headA = headA.node;
  69. }
  70. while (headB !=null) {
  71. if (map.containsKey(headB)){
  72. return headB;
  73. }
  74. headB = headB.node;
  75. }
  76. return null;
  77. }

相交链表元素为:ListNode{val=3, node=ListNode{val=4, node=ListNode{val=5, node=null}}}
相交链表元素为:ListNode{val=3, node=ListNode{val=4, node=ListNode{val=5, node=null}}}

【LeetCode-160】相交链表_哔哩哔哩_bilibili

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

闽ICP备14008679号