
问题
请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。
现有一个链表 — head = [4,5,1,9],它可以表示为:
4 -> 5 -> 1 -> 9
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.
输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.
说明:
链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Given linked list — head = [4,5,1,9], which looks like following:
4 -> 5 -> 1 -> 9
Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.
Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.
Note:
The linked list will have at least two elements.
All of the nodes’ values will be unique.
The given node will not be the tail and it will always be a valid node of the linked list.
Do not return anything from your function.
示例
public class Program { public static void Main(string[] args) { var head = new ListNode(1) { next = new ListNode(2) { next = new ListNode(3) { next = new ListNode(4) { next = new ListNode(5) } } } }; DeleteNode(head.next.next); ShowArray(head); Console.ReadKey(); } private static void ShowArray(ListNode list) { var node = list; while(node != null) { Console.Write($"{node.val} "); node = node.next; } Console.WriteLine(); } private static void DeleteNode(ListNode node) { //先复制下一个节点的值 node.val = node.next.val; //再把下一节点的指针指向下下一个节点 node.next = node.next.next; } public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; } } }
以上给出1种算法实现,以下是这个案例的输出结果:
1 2 4 5
分析:
显而易见,以上算法的时间复杂度为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3832。