要找到链表的倒数第三个节点,可以使用双指针的方法。首先,定义两个指针p1和p2,初始时都指向链表的头节点。
然后,将p2向后移动3个位置,使得p1和p2之间相隔3个节点。
接下来,同时移动p1和p2,直到p2指向链表的尾节点。此时,p1所指向的节点就是倒数第三个节点。这是因为p2移动了n-3个位置,而p1和p2之间相隔3个节点,所以p1移动了n-3+3=n个位置,即到达了倒数第三个节点。最后,返回p1所指向的节点即可。这种方法的时间复杂度为O(n),其中n是链表的长度。
从头遍历第一次,求出单链表长度L;
再遍历一次,第L-3+1个节点就是从尾部倒数第3个节点。
但这种方法需要遍历两遍。