【剑指offer-56】20190908/02 删除链表中重复的结点

【剑指offer-56】删除链表中重复的结点

  • 考点:链表
  • 时间限制:1秒
  • 空间限制:32768K
  • 在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
  • 自己做出来了吗:
  • 时间:

思路:

首先添加一个头节点,以方便碰到第一个,第二个节点就相同的情况

2.设置 pre ,last 指针, pre指针指向当前确定不重复的那个节点,而last指针相当于工作指针,一直往后面搜索。

代码:
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        // 只有0个或者1个节点
        if (pHead == null || pHead.next == null) {
            return pHead;
        }
        
        ListNode Head = new ListNode(0);
        Head.next = pHead; // 新建一个头结点
        
        ListNode pre = Head; // 新的头结点
        ListNode last = Head.next; // 当前pHead
        
        while (last != null) {
            // 工作节点的值和下一个节点的值相同了
            if (last.next != null && last.val == last.next.val) {
                // 找到最后一个相同的节点
                while (last.next != null && last.val == last.next.val) {
                    last = last.next;
                }
                // last.next是不同了
                pre.next = last.next;
                // next指针继续往后移动
                last = last.next;
            } else {
                // 分别移动
                pre = pre.next;
                last = last.next;
            }
        }
        // 返回真正的头结点
        return Head.next;

    }
}
我的问题:
  1. 有可能从头结点开始就是重复的要被删掉了,所以要创建一个新的节点保存头结点。
  2. 需要找到一直重复的节点,所以last节点就开始遍历,直到找到下一个不相同了,所以last.next的节点已经是新的不是重复的节点了

其他思路1:

递归的代码:

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        // 只有0个或者1个节点
        if (pHead == null || pHead.next == null) {
            return pHead;
        }
        
        // 当前节点是重复的节点
        if (pHead.val == pHead.next.val) {
            ListNode node = pHead.next;
            while (node != null && node.val == pHead.val) {
                // 跳过值与当前结点相同的全部结点,找到第一个与当前结点不同的结点
                node = node.next;
            }
            return deleteDuplication(node); // 从第一个与当前结点不同的结点开始递归
        } else {
            pHead.next = deleteDuplication(pHead.next); // 保留当前结点,从下一个结点开始递归
            return pHead;
        }
    }
}

上一篇:剑指Offer(链表)-删除链表中重复的节点


下一篇:【Leetcode 142】js 环形链表Ⅱ(链表环的入口节点)