本文主要是介绍在O(1)时间内删除链表结点删除链表中重复节点,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意描述:给定单向链表的头指针和一个结点指针,定义一个函数在O(1)时间删除该结点
解题思路:要求在O(1)时间内删除结点,则可以这样考虑:将给定结点后继结点的值赋给给定结点,然后删除给定结点的后继结点即可
void DeleteNode(ListNode** pHead, ListNode* pToBeDeleted) {if (!pHead || !pToBeDeleted)return;if (pToBeDeleted->m_pNext != NULL) {//如果要删除的结点不是尾结点ListNode* pNode = pToBeDeleted->m_pNext;pToBeDeleted->m_nValue = pNode->m_nValue;pToBeDeleted->m_pNext = pNode->m_pNext;delete pNode;pNode = NULL;}else if(*pHead == pToBeDeleted){//如果要删除的结点只有一个头结点delete pToBeDeleted;pToBeDeleted = NULL;pHead = NULL;}else {//链表有多个结点,且删除的是尾结点ListNode* p = *pHead;while (p->m_pNext != pToBeDeleted)p = p->m_pNext;p->m_pNext = NULL;delete pToBeDeleted;pToBeDeleted = NULL;}}
题意描述:删除链表中重复节点
1、重复节点只保留一个
/*public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}
*/
public class Solution {public ListNode deleteDuplication(ListNode pHead){if (pHead == null || pHead.next == null) {return pHead;}ListNode newHead = pHead;ListNode curNode = pHead.next;while (curNode != null) {if(curNode.val == pHead.val) {curNode = curNode.next;pHead.next = curNode;} else {pHead = pHead.next;curNode = curNode.next;}}return newHead;}
}
2、重复节点不保留
/*public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}
*/
public class Solution {public ListNode deleteDuplication(ListNode pHead){if (pHead == null || pHead.next == null) {return pHead;}ListNode newHead = new ListNode(-1);newHead.next = pHead;ListNode last = newHead;ListNode cur = pHead;while(cur != null && cur.next != null) {if(cur.val == cur.next.val) {int val = cur.val;while (cur != null && cur.val == val) {cur = cur.next;}last.next = cur;} else {last = cur;cur = cur.next;}}return newHead.next;}
}
这篇关于在O(1)时间内删除链表结点删除链表中重复节点的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!