lc160 怎样用递归写法呢？

来源：5-3 设立链表的虚拟头结点 Remove Linked List Elements

Y1ng

2019-11-22

lc160，虽然“Your code should preferably run in O(n) time and use only O(1) memory. ”。
直觉上这题可以用递归。但我尝试写一直有bug，最主要的原因是子函数的input有问题。
请问有没有人能给一个递归写法，谢谢！

写回答

2回答

Y1ng

提问者

2019-11-22

提供一个性能较好的非递归写法：

// O(m + n)
// O(1)
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(getLastNode(headA) != getLastNode(headB)) {
            return null;
        }
        
        ListNode pA = headA, pB = headB;
        while(pA != pB) {
            pA = (pA.next == null)? headB : pA.next;
            pB = (pB.next == null)? headA : pB.next;
        }
        return pA;
    }
    
    private ListNode getLastNode(ListNode head) {
        ListNode curr = head;
        while(curr != null && curr.next != null) {
            curr = curr.next;
        }
        return curr;
    }
}

一开始依然得判断交集是否为null