给定一个头结点为 head
的非空单链表,返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
使用常规方法,也就是先遍历链表获得链表长度,随后获得中间结点的下标,再次遍历链表到中间节点位置,返回该节点即可
设链表的长度为size
,需要注意的是不需要考虑链表长度的奇偶性,因为当长度为偶数时,返回的是size/2+1
,长度为奇数时,返回的是size/2+1
,是一样的
时间复杂度为O(n)
public ListNode middleNode(ListNode head) { ListNode curNode = head; int size = 0; while(curNode!=null){ size++; curNode = curNode.next; } curNode = head; //因为head不为null,所以count初始值为1 int count = 1; while(count < size/2+1){ curNode = curNode.next; count++; } return curNode; }
使用快慢指针a
,b
a指针
每次只走一步,b指针
每次只走两步
等到b指针
无法在移动的时候,a指针
已经指向目标节点
注意,不管链表长度的奇偶性如何…代码解释…
public ListNode middleNode(ListNode head) { //firstNode指针走两步 ListNode firstNode = head; //lastNode指针走一步 ListNode lastNode = head; //跳出循环时,firstNode指针已经指向null或者firstNode.next指针已经指向null //这里大家可以使用手指验算,很容易想通的 //只不过要注意的是,是从第一根手指开始走哦 //也就是说第一次走完之后,firstNode指针应该指向第三根手指 while(firstNode!=null && firstNode.next != null){ lastNode = lastNode.next; firstNode = firstNode.next.next; } return lastNode; }