• 题目描述:在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表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;
      }