876. Middle of the Linked List 利用快慢指针求链表的中间节点

快来打我* 2022-10-30 11:24 27阅读 0赞

比如链表结构为`1->2->3->4->5` 此时中间节点为 `3`  
如果链表结构为 `1->2->3->4` 此时中间节点为`2`或者`3`

### 节点定义 ###

利用golang来描述这个实现过程，ListNode的节点实现

type ListNode struct { 
    	Val  int
    	Next *ListNode
    }

### 实现 ###

func middleNode(head *ListNode) *ListNode { 
    	slow := head
    	fast := head
    	// 循环遍历完，fast一定指向最后一个节点
    	for fast != nil && fast.Next != nil { 
    		slow = slow.Next
    		fast = fast.Next.Next
    	}
    	return slow
    }

### 通用化 ###

什么叫通用化，实际上有的需求需要求链表的某一段的中间节点  
比如链表为`1->2->3->4->5` ，我们需要求`1->2->3`这一段的中间节点，此时`head`为1,尾节点`tail`为`3`，我们参考上面求整个链表的中间节点的过程，`head`为`1`，`tail`为`5`,在求整个链表的中间节点的时候，我们判定不等于的条件为`nil`也就是空，在求部分的时候，我们只需要将这个`nil`改为`tail.Next`即可。

可以看作：前闭后开`[head, tail.Next)`

func middleNode(head *ListNode, tail *ListNode) *ListNode { 
    	slow := head
    	fast := head
    	// 循环遍历完，fast一定指向最后一个节点
    	for fast != tail && fast.Next != tail { 
    		slow = slow.Next
    		fast = fast.Next.Next
    	}
    	return slow
    }

比如我们有链表`1->2->3->4->5` 有两个指针，一个`head`指向`1`, 一个`tail`指向`4`，那么调用方法 `middleNode(head, tail)` 求的是 `1->2->3`这个链表的的中间节点，也就是求`[1, 4)`的中间节点，最终返回的指针指向`2`.