LeetCode 83. Remove Duplicates from Sorted List

题目

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.

分析

删除有序链表中的重复节点

  • 输入:一个有重复节点的有序链表
  • 输出:一个去重后的有序链表

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
cur = head
while cur:
if cur.next and cur.next.val == cur.val:
cur.next = cur.next.next # skip duplicated node
else:
cur = cur.next # not duplicate of current node, move to next node
return head

点评

首先备份头结点,用 cur 来作为游标指针,遍历链表,每次遍历时,判断是否有下一个节点,且下一个节点的值和当前节点的值相等,是的话,跳过下一个节点(将下一个节点更新为下一个节点的下一个节点),否则更新游标指针遍历下一个节点