剑指offer56 删除链表中重复节点

剑指offer56

删除链表中重复节点

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

示例

输入

{1,2,3,3,4,4,5}

输出

{1,2,5}

思路

非递归：

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

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)
    {
        if(pHead==null || pHead.next==null)return pHead;
        //首先添加一个头节点，以便碰到第一个第二个节点就相同的情况
        ListNode head = new ListNode(0);
        head.next = pHead;
        //设置 pre ，last 指针， pre指针指向当前确定不重复的那个节点，而last指针相当于工作指针，一直往后面搜索。
        ListNode pre = head;
        ListNode last = head.next;
        while(last!=null){
            if(last.next!=null && last.val==last.next.val){
                //找到最后一个相同节点
                while(last.next!=null && last.val==last.next.val){
                    last = last.next;
                }
                pre.next = last.next;
                last = last.next;
            }else{
                pre = pre.next;
                last = last.next;
            }
        }
        return head.next;
    }
}

---

递归

    public ListNode deleteDuplication(ListNode pHead){
        if(pHead == null){
            return null;
        }        
        if(pHead.next == null){
            return pHead;
        }
        //两个循环，用来应付“1-1-2-2-3-3-4-5…”格式的连续重复结点
        while(pHead != null && pHead.next != null && pHead.val == pHead.next.val){
            while(pHead != null && pHead.next != null && pHead.val == pHead.next.val){
                pHead = pHead.next;
            }
             pHead = pHead.next;
        }
        if(pHead!=null ){
            pHead.next = deleteDuplication(pHead.next);
        }
        return pHead;
    }