首页 > 编程语言 > 详细

LeetCode 83 Remove Duplicates from Sorted List(从已排序链表中移除重复元素)(*)

时间:2016-01-14 09:48:52      阅读:143      评论:0      收藏:0      [点我收藏+]

翻译

给定一个已排序链表,删除所有重复元素让每个元素只出现一次。

例如:
给定 1->1->2, 返回 1->2。
给定 1->1->2->3->3, 返回 1->2->3

原文

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

分析

大家可以先看看这篇博客:LeetCode 206 Reverse Linked List(反转链表)(四步将递归改写成迭代)(*) ,然后再回过来看,因为这一篇中我用作图的方式解释了针对反转链表的一系列过程,本题也是大同小异的。

切入正题,首先我们应该先判断是否为空:

if (head == NULL) return NULL;
if (head->next == NULL) return head;    

但是这两行代码是可以简写的:

if (head == NULL || head->next == NULL) return head;

下面是一个循环语句:

while (head->next) {
    if (head->val == head->next->val) {
        head->next = head->next->next;
    }
    else {
        head = head->next;
    }   
}    

意思非常简单,首先判断当前的节点的值与下一个节点的值是否相等,如果相等,则将下下一个节点赋值给下一个节点。

1——1——2——3——3
改写成:
1——2——3——3

此时head还在1上,但为什么不将其移动到2上呢,也就是说代码为什么不是这样的:

while (head->next) {
    if (head->val == head->next->val) {
        head->next = head->next->next;
        head = head->next;
    }
    else {
        head = head->next;
    }   
}    

理由很简单,例如:

1——1——1——2——3——3
经过第一次变换后:
1——1——2——3——3
如果贸然将head移动到下一个节点上,那么下一次的对比就是对比1和2了,显然是不合理的。

到了这里移除操作就已经完成了,但是能够直接returnhead吗,显然也是不能的,因为head已经移动到了最后一个节点了。

所以应该在while循环之前就设置了新的head作为记录,最后返回它就好了。

ListNode* newHead = head;
while(){}
return newHead;

代码

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* newNode = head;
        while (head->next) {
            if (head->val == head->next->val)
                head->next = head->next->next;
            else
                head = head->next;
        }
        return newNode;
    }
};

LeetCode 83 Remove Duplicates from Sorted List(从已排序链表中移除重复元素)(*)

原文:http://blog.csdn.net/nomasp/article/details/50514648

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!