剑指Offer——删除链表中重复的结点

By AverageJoeWang
 标签:

删除链表中重复的结点

  • 题目描述

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

  • 解题思路

需要两个指针,一个指向前一个节点preNode,另一个指向当前节点node,如果遇到相等的节点,node向后移动,preNode不动,存下node.val方便后面的比较,直到遇到node和node.next不相等,preNode就可以指向node.next

  • 代码实现
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        ListNode preNode = null;
        ListNode node = pHead;
        while (node != null) {
            if (node.next != null && node.val == node.next.val) {
                int value = node.val;
                while (node.next != null && node.next.val == value) {
                    node = node.next;
                }
                if (preNode == null) {
                    pHead = node.next;
                } else {
                    preNode.next = node.next;
                }
            } else {
                preNode = node;
            }
            node = node.next;
        }
        return pHead;
    }
}