题目描述
给定一个单链表中的表头和一个等待被删除的节点(非表头或表尾)。请在在O(1)时间复杂度删除该链表节点。并在删除该节点后，返回表头。
样例 给定 1->2->3->4，和节点 3，返回 1->2->4。
(372) Delete Node in the Middle of Singly Linked List
解题思路
删除链表节点，最普通的方法就是遍历链表，复杂度为。 如果我们把删除节点的下一个结点的值赋值给要删除的结点，然后删除这个结点，这相当于删除了需要删除的那个结点。因为我们很容易获取到删除节点的下一个节点，所以复杂度只需要，注意题目要求非表头或表尾。 比如样例 1->2->3->4->NULL 删除节点 3 。第一步将节点3的下一个节点的值4赋值给当前节点。变成 1->2->4->4->NULL，然后将就 4 这个结点删除，就达到目的了。 1->2->4->NULL
如果删除的节点的是头节点，，把头结点指向NULL。 如果删除的节点的是尾节点，那只能从头遍历到头节点的上一个结点。
代码实现(非表头或表尾)/** * Definition of ListNode * class ListNode { * public: *int val; *ListNode *next; *ListNode(int val) { *this->val = val; *this->next = NULL; *} * } */class Solution {public:/*** @param node: a node in the list should be deleted* @return: nothing*/void deleteNode(ListNode *node) {// write your code hereif(node == NULL)return;if(node->next != NULL){ListNode *pNext = node->next;node->val = pNext->val;node->next = pNext->next;delete pNext;pNext = NULL;}}};代码实现 void deleteNode(ListNode **head, ListNode *node) {)return;if(node->next != NULL){ListNode *pNext = node->next;node->val = pNext->val;node->next = pNext->next;delete pNext;pNext = NULL;}else if(*head == node) //删除的节点是头节点{delete node;node = NULL;*head = NULL;}else//删除的是尾节点{ListNode *pNode = *head;while(pNode->next != node){pNode = pNode->next;}pNode->next = NULL;delete node;node = NULL;}}
关于爱情的句子：情不知所起，一往而情深。
