2024牛客春招冲刺题单 ONT97 牛牛的递增之旅【中等链表 Java,Go,PHP】

题目

在这里插入图片描述
题目链接：
https://www.nowcoder.com/practice/e463addab7d548819d6b6483335651b5

思路

核心：链表中删除节点。链表中增删改查节点，最好新建一个虚拟头结点start,end，
然后end链接上符合条件的已经存在的节点，最后返回start.next

参考答案Java

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode removeDuplicates (ListNode head) {
        Map<Integer, Integer> map = new HashMap<>();
        ListNode cur = head;
        while (cur != null) {
            int k = cur.val;

            if (!map.containsKey(k))
                map.put(k, 0);

            map.put(k, map.get(k) + 1);

            cur = cur.next;
        }

         cur = head;
         ListNode start = new ListNode(-1); //新建虚拟头结点
         ListNode end = start;
        while(cur!=null){

            ListNode next = cur.next;
            int k = cur.val;
            if(map.get(k) != 0){ //k没在以start开头的链表中
                cur.next = null;
                end.next = cur;
                end = cur;
                map.put(k,0);
            }

            cur = next;

        }

        return start.next;
    }
}

参考答案Go

package main

import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
*/
func removeDuplicates( head *ListNode ) *ListNode {
    map1:=map[int]int{}
    cur:=head

    for cur!=nil {
        k:=cur.Val
        _,ok:=map1[k]
        if !ok{
            map1[k] =0
        }

        map1[k] = map1[k]+1
        cur = cur.Next
    }

    cur= head
    start:=&ListNode{-1,nil}
    end:=start 
    for cur!=nil {
        next:=cur.Next

        k:=cur.Val

        cnt,_:=map1[k]
        if cnt !=0{
            cur.Next=nil
            end.Next = cur
            end=cur 
            map1[k] =0
        }
        cur =next
    }
    return start.Next
}

参考答案PHP

<?php

/*class ListNode{
    var $val;
    var $next = NULL;
    function __construct($x){
        $this->val = $x;
    }
}*/

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
function removeDuplicates( $head )
{
    $map = array();
    $cur = $head;
    while($cur!=null){
        $k = $cur->val;
        if(!isset($map[$k]))
            $map[$k] =0;

        $map[$k]+=1;
        $cur =$cur->next;
    }

    $cur = $head;
    $start =new ListNode(-1);
    $end = $start;
    while($cur!=null){
        $next = $cur->next;
        $k =$cur->val;

        if($map[$k]!=0){
            $cur->next =null;
            $end->next = $cur;
            $end =$cur;
            $map[$k] =0;
        }

        $cur = $next;
    }
    return $start->next;
}