WalkingSun

删除排序链表中的重复元素

2019/04/25 leetcode 链表

链表处理

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

力扣链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

示例 1:

输入: 1->1->2

输出: 1->2

示例 2:

输入: 1->1->2->3->3

输出: 1->2->3

<?php
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution {

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function deleteDuplicates($head) {
        $pre = $head;
        while( $pre->next!==null ){
            if($pre->val==$pre->next->val){
                $pre->next=$pre->next?$pre->next->next:null;
            }else{
               $pre=$pre->next; 
            }
        }
        
        return $head;
    }
}

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

链接 https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/

示例 1:

输入: 1->2->3->3->4->4->5 输出: 1->2->5

示例 2:

输入: 1->1->1->2->3

输出: 2->3

<?php
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution {

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function deleteDuplicates($head) {
        $pre = new ListNode(0);
        $pre->next = $head;
        $head=$pre;              //新的链表头
        while( $pre->next){
            $left = $pre->next;         //左指针
            $right = $left;             //右指针
            
            while ($right->next && $right->next->val == $left->val){
                $right = $right->next;
            }
            
            if($right == $left){
                $pre = $pre->next;
            }else{
                $pre->next = $right->next;
            }
            
        }
        
        return $head->next;
    }
}

Search

    Table of Contents