不积跬步，无以至千里
【= 链表的中间节点 =】
题目描述
解题思路
思路一：可以理解为数组的中间元素，长度奇数时中间元素为 len/2 反之中间元素为len/2+1 其次需要注意链表的操作，是不同于数组的
思路二：快慢指针 快指针每次移动2，慢指针每次移动1，当快指针指向null时 慢指针也刚好指向中间节点或者下中节点
关于链表的相关知识，可以参考：数据结构与算法-链表
解题方法
- PHP
// 思路一
function middleNode($head) {
$new = [];
while ($head) {
$new[] = $head;
$head = $head->next;
}
return $new[floor(count($new)/2)];
}
// 思路二
function middleNode($head) {
$slow = $head;
$fast = $head;
while($fast != null && $fast->next != null) {
$slow=$slow->next;
$fast = $fast->next->next;
}
return $slow;
}
- GO
//思路一
func middleNode(head *ListNode) *ListNode {
var arr []*ListNode
for head != nil {
arr = append(arr, head)
head = head.Next
}
return arr[len(arr)/2]
}
// 思路二
func middleNode(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow, fast = slow.Next, fast.Next.Next
}
return slow
}
【= 删除链表倒数第N个节点 =】
题目描述
解题思路
1 获取链表长度
2 搜索待删除的前一个节点 L-n
2 删除节点
解题方法
- PHP
function removeNthFromEnd($head, $n) {
// 虚拟头节点
$newHead = new ListNode(null);
$len = 0;
$newHead->next = $head;
// 求链表长度
while($head) {
$head = $head->next;
$len++;
}
$cur = $newHead;
for ($i=1;$i<=$len-$n;$i++) {
// 找出待删除的前一个节点
$cur = $cur->next;
}
// 删除节点
$cur->next = $cur->next->next;
return $newHead->next;
}
- GO
func removeNthFromEnd(head *ListNode, n int) *ListNode {
new := &ListNode{0, head}
// 获取链表长度
len := 0
for (head != nil) {
head = head.Next
len++
}
cur := new
// 获取待删除前一个节点
for i := 0; i < len-n; i++ {
cur = cur.Next
}
// 删除节点
cur.Next = cur.Next.Next
return new.Next
}