题目描述:在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
这道题一看,以为很容易,一做就懵;后来想到可以用栈来处理,虽然代码行数有点多,但是思路还是比较清晰的;
思路:
维护两个栈,将所有不重复的节点加入到stack1中;
所有节点出栈,放入stackHelper栈中;
将节点从stackHelper中弹出并建立链接,
注意:stackHelper中弹出的最后一个节点,last.next = null
public ListNode deleteDuplication(ListNode pHead) { Stack<ListNode> stack1 = new Stack<>(); Stack<ListNode> stackHelper = new Stack<>(); boolean isDup = false; while (pHead != null){ // 栈为空直接入栈 if (stack1.empty()) { stack1.add(pHead); pHead = pHead.next; }else { // 栈不为空,比较当前节点值和栈顶节点值,不相等,入栈 if(stack1.peek().val != pHead.val) { stack1.add(pHead); pHead = pHead.next; }else { // 栈不为空,当前节点值等于栈顶节点值,找到当前节点后第一个不等于栈顶的节点,栈顶节点出栈,不等于栈顶的节点入栈。 while (pHead != null && pHead.val == stack1.peek().val){ pHead = pHead.next; } stack1.pop(); if(pHead == null) break; stack1.add(pHead); pHead = pHead.next; } } } // 如果stack1为空,返回空 if (stack1.empty()) { return null; } //将stack1中所有节点加入stackHelper while (!stack1.empty()){ stackHelper.add(stack1.pop()); } // 保留第一个节点 ListNode first = stackHelper.pop(); ListNode worker = first; // 将节点建立联系 while (!stackHelper.empty()){ worker.next = stackHelper.pop(); worker = worker.next; } // 最后一个节点,断开原先连接 worker.next = null; return first; }