【剑指offer-56】删除链表中重复的结点
- 考点:链表
- 时间限制:1秒
- 空间限制:32768K
- 在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5
- 自己做出来了吗:
- 时间:
思路:
首先添加一个头节点,以方便碰到第一个,第二个节点就相同的情况
2.设置 pre ,last 指针, pre指针指向当前确定不重复的那个节点,而last指针相当于工作指针,一直往后面搜索。
代码:
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode deleteDuplication(ListNode pHead)
{
// 只有0个或者1个节点
if (pHead == null || pHead.next == null) {
return pHead;
}
ListNode Head = new ListNode(0);
Head.next = pHead; // 新建一个头结点
ListNode pre = Head; // 新的头结点
ListNode last = 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;
}
// last.next是不同了
pre.next = last.next;
// next指针继续往后移动
last = last.next;
} else {
// 分别移动
pre = pre.next;
last = last.next;
}
}
// 返回真正的头结点
return Head.next;
}
}
我的问题:
- 有可能从头结点开始就是重复的要被删掉了,所以要创建一个新的节点保存头结点。
- 需要找到一直重复的节点,所以last节点就开始遍历,直到找到下一个不相同了,所以last.next的节点已经是新的不是重复的节点了
其他思路1:
递归的代码:
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode deleteDuplication(ListNode pHead)
{
// 只有0个或者1个节点
if (pHead == null || pHead.next == null) {
return pHead;
}
// 当前节点是重复的节点
if (pHead.val == pHead.next.val) {
ListNode node = pHead.next;
while (node != null && node.val == pHead.val) {
// 跳过值与当前结点相同的全部结点,找到第一个与当前结点不同的结点
node = node.next;
}
return deleteDuplication(node); // 从第一个与当前结点不同的结点开始递归
} else {
pHead.next = deleteDuplication(pHead.next); // 保留当前结点,从下一个结点开始递归
return pHead;
}
}
}