• 两个链表的第一个公共结点
    • 题目
    • 解决思路
      • 空间复杂度 O(n) 的算法
      • 空间复杂度 O(1) 的算法

    两个链表的第一个公共结点

    题目

    牛客网

    输入两个链表,找出它们的第一个公共结点。

    解决思路

    空间复杂度 O(n) 的算法

    1. 使用辅助容器,保存第一个链表的所有元素
    2. 遍历第二个链表,并对比当前节点是否在辅助容器中
    1. /**
    2. * 空间 O(n)
    3. *
    4. * @param pHead1
    5. * @param pHead2
    6. * @return
    7. */
    8. public ListNode FindFirstCommonNode_1(ListNode pHead1, ListNode pHead2) {
    9. Set<ListNode> node1s = new HashSet<>();
    10. while (pHead1 != null) {
    11. node1s.add(pHead1);
    12. pHead1 = pHead1.next;
    13. }
    14. while (pHead2 != null) {
    15. if (node1s.contains(pHead2)) {
    16. return pHead2;
    17. }
    18. pHead2 = pHead2.next;
    19. }
    20. return null;
    21. }

    空间复杂度 O(1) 的算法

    1. 由于两个链表有可能不一样长,首先通过遍历找到他们的长度
    2. 移动较长的那个链表,使得两个链表长度一致
    3. 同步遍历两个链表

    原理:如果两个链表相交,那么它们一定有相同的尾节点

    1. /**
    2. * 空间 O(1)
    3. *
    4. * @param pHead1
    5. * @param pHead2
    6. * @return
    7. */
    8. public ListNode FindFirstCommonNode_2(ListNode pHead1, ListNode pHead2) {
    9. int len1 = 0, len2 = 0;
    10. ListNode cursor1 = pHead1, cursor2 = pHead2;
    11. while (cursor1 != null) {
    12. cursor1 = cursor1.next;
    13. len1++;
    14. }
    15. while (cursor2 != null) {
    16. cursor2 = cursor2.next;
    17. len2++;
    18. }
    19. cursor1 = pHead1;
    20. cursor2 = pHead2;
    21. if (len1 > len2) {
    22. int i = len1;
    23. while (i != len2) {
    24. cursor1 = cursor1.next;
    25. i--;
    26. }
    27. } else if (len1 < len2) {
    28. int i = len2;
    29. while (i != len1) {
    30. cursor2 = cursor2.next;
    31. i--;
    32. }
    33. }
    34. while (cursor1 != null && cursor2 != null) {
    35. if (cursor1 == cursor2) {
    36. return cursor1;
    37. }
    38. cursor1 = cursor1.next;
    39. cursor2 = cursor2.next;
    40. }
    41. return null;
    42. }