C/C++教程

leetcode算法入门系列学习五『链表中间节点| 删除链表的倒数第N个节点』

本文主要是介绍leetcode算法入门系列学习五『链表中间节点| 删除链表的倒数第N个节点』,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

不积跬步,无以至千里

  • 【= 链表的中间节点 =】
    • 题目描述
    • 解题思路
    • 解题方法
  • 【= 删除链表倒数第N个节点 =】
    • 题目描述
    • 解题思路
    • 解题方法

【= 链表的中间节点 =】

题目描述

传送门

解题思路

思路一:可以理解为数组的中间元素,长度奇数时中间元素为 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
}

在这里插入图片描述

这篇关于leetcode算法入门系列学习五『链表中间节点| 删除链表的倒数第N个节点』的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!