文档章节

删除链表中重复的节点

G
 Garphy
发布于 2019/11/13 14:31
字数 429
阅读 11
收藏 0

解题思路:

  1. 我们每次都判断当前结点的值与下一个节点的值是否重复
  2. 如果重复就循环寻找下一个不重复的节点,将他们链接到——新链表的尾部(其实就是删除重复的节点)

 

public ListNode deleteDuplication(ListNode pHead) {
    if (pHead == null || pHead.next == null)
        return pHead;
    ListNode next = pHead.next;
    if (pHead.val == next.val) {
        while (next != null && pHead.val == next.val)
            next = next.next;
        return deleteDuplication(next);
    } else {
        pHead.next = deleteDuplication(pHead.next);
        return pHead;
    }
}

非递归版:

public class Solution {
   	public ListNode deleteDuplication(ListNode pHead) {
		if (pHead == null || pHead.next == null) {
			return pHead;
		}
		ListNode Head = new ListNode(0);
		Head.next = pHead;
		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;
	}
}

 

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

2.设置 pre ,last 指针, pre指针指向当前确定不重复的那个节点,而last指针相当于工作指针,一直往后面搜索。

这是我写的,有错误!

public class Solution {
 public ListNode deleteDuplication(ListNode pHead) {
		if (pHead == null || pHead.next == null) {
			return pHead;
		}
		ListNode Head = new ListNode(0);
		ListNode pre = Head;
		ListNode last = Head.next;
		Head.next = pHead;
		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;
	}
}

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

对应输出应该为:

{1,2,5}

你的输出为:

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

这段代码的顺序不能置换


        ListNode Head = new ListNode(0);
		Head.next = pHead;
		ListNode pre = Head;
		ListNode last = Head.next;

 

© 著作权归作者所有

G
粉丝 0
博文 206
码字总数 88735
作品 0
私信 提问
删除链表中重复的节点

一道来自剑指offer的编程题,题目描述如下: 在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为...

zhaokx3
2017/03/15
0
0
[算法总结] 一文搞懂面试链表题

本文首发于我的个人博客:尾尾部落 链表是面试过程中经常被问到的,这里把剑指offer 和 LeetCode 中的相关题目做一个汇总,方便复习。 1. 在 O(1) 时间删除链表节点 题目描述:给定单向链表的...

繁著
2018/08/28
0
0
Week 26 0911-0917

question 1:寻找二叉树中第二小的数 我的答案: 暴力解法,直接将树转换成列表 别人的答案: 利用题目的信息:假如节点有子节点的话(有子节点一定是左,右节点都有),这个根节点就是最小的...

vincehxb
2017/09/20
0
0
[剑指offer] 删除链表中重复的结点

本文首发于我的个人博客:尾尾部落 题目描述 在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为...

繁著
2018/07/28
0
0
《剑指offer》链表专题 (牛客10.23)

难度 题目 知识点 03. 返回链表的反序 vector 递归,C++ STL reverse() * 14. 链表中倒数第k个结点 指针操作 15. 反转链表 头插法,递归 16. 合并两个有序链表 指针操作 *** 25. 复杂链表的复...

武藏小次郎
2019/10/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

[科普向]2.4G信道怎么选?

今天我们来讲讲路由器信道的问题,这里主要讲2.4G频段的信道怎么选。 首先,我们来看下2.4G信道划分图! 由于地区的不同,有些设备不支持11以上的信道,所以我们重点选择1到11信道来讲解。 ...

FalconChen
35分钟前
8
0
Mysql清理binlog日志

Mysql清理binlog日志 转载 Karryyyyyy 最后发布于2019-03-02 01:09:23 阅读数 985 收藏 展开 1.查看binlog日志 mysql> show binary logs;+------------------+------------+| Log_nam......

rootliu
44分钟前
7
0
javafx 实现controller间的数据传递

下面总共是两个帖子的内容,分别是: https://blog.csdn.net/u012880338/article/details/69063776 https://www.jianshu.com/p/6950b68970da avaFXController之间通信 问题背景: 最近在做毕...

whoisliang
46分钟前
9
0
素小暖讲hibernate

本文主要讲解hibernate框架,ORM的概念和hibernate入门,相信大家看了之后就会使用hibernate了。 欲速则不达,欲达则欲速! 一、基本概念 hibernate是一种ORM框架,全称为Object_Relative D...

素小暖OSC
50分钟前
12
0
如何使用Selenium WebDriver截屏

有谁知道是否可以使用Selenium WebDriver截屏? (注:不是硒RC) #1楼 吉顿 import org.openqa.selenium.OutputType as OutputTypeimport org.apache.commons.io.FileUtils as FileUtils......

技术盛宴
58分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部