删除链表中重复的结点

题目描述

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

链表的定义

//链表的定义
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

PS：本文主要的解法以非递归解法为主，一切可以以递归解的题目都可以变成非递归解法。

递归代码（加注释）

package nowcoder;

/**
 * @author god-jiang
 * @date 2020/2/6  11:33
 */
public class DeleteDuplication {
    //链表定义
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    //递归解法
    public ListNode deleteDuplication(ListNode pHead) {
        //base case
        if (pHead == null)
            return null;
        if (pHead.next == null)
            return pHead;
        ListNode cur;
        //对重复结点的处理
        if (pHead.val == pHead.next.val) {
            cur = pHead.next.next;
            //遍历到没有重复结点的位置
            while (cur != null && cur.val == pHead.val) {
                cur = cur.next;
            }
            return deleteDuplication(cur);
        }
        //没有重复结点
        cur = pHead.next;
        pHead.next = deleteDuplication(cur);
        return pHead;
    }
}

通过截图

PS：递归解法的题目都是需要你自己弄懂他的过程，就好比我当初学习递归的第一个例子就是汉诺塔，我也很懵逼，这究竟是什么东西！！！然后花了一个晚上在图书馆一直看课本上的例子和代码，然后就会恍然大悟，原来递归就是这样的。所以递归的思路我水平有限，不知道怎么解释，希望你们自己好好弄懂。

非递归思路

首先new一个头节点初始化为0，防止第一个结点和第二个结点相同的情况
设置pre和last指针，pre指针指向当前确定不重复的结点，last指针就一直向后搜索

代码（加注释）

package nowcoder;

/**
 * @author god-jiang
 * @date 2020/2/6  11:53
 */
public class DeleteDuplication {
    //链表定义
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    //非递归解法
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return pHead;
        }
        //初始化一个0为头结点，防止pHead的第一个结点和第二个结点相同的情况
        ListNode head = new ListNode(0);
        head.next = pHead;
        //pre指向确定不重复的结点
        ListNode pre = head;
        ListNode last = head.next;
        while (last != null) {
            //如果last和后面的指针相同
            if (last.next != null && last.val == last.next.val) {
                //找到last往后不重复的结点的位置
                while (last.next != null && last.val == last.next.val) {
                    last = last.next;
                }
                //相当于删除重复的结点
                pre.next = last.next;
                last = last.next;
            } else {
                //如果不重复，pre和last分别往后移动
                pre = pre.next;
                last = last.next;
            }
        }
        return head.next;
    }

}