继续关于linked list的算法题：
给定一个排序链表，删除所有重复的元素使得每个元素只留下一个。
案例：
给定 1->1->2，返回 1->2
给定 1->1->2->3->3，返回 1->2->3
解题思路：
这道题很简单，只需要比较当前节点和下一个节点，相同，则当前节点的指针指向下一节点的下一节点，不相同，递归下一节点。还是要注意同样的问题，单向链表是只能向后不能向前的，所以，要保留首节点。
# 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
"""
if not head:
return None
pre = head
while pre.next:
if pre.val == pre.next.val:
pre.next = pre.next.next
else:
pre = pre.next
return head
我们继续来看另外一道题目
给定一个链表，对每两个相邻的结点作交换并返回头节点。
例如：
给定 1->2->3->4，你应该返回 2->1->4->3。
你的算法应该只使用额外的常数空间。不要修改列表中的值，只有节点本身可以更改。
解题思路：
这里思路很明确，每次循环两个变量，在循环中维护两个变量，temp1和temp2,分别代表每当前次循环的第一个节点和第二个节点,交换他们的位置，并把原来的pre指针指向调整位置后的第一个节点，第二个节点的指针指向后续指针。dump代表新列表的头元素，pre代表每次循环的前置指针元素。代码如下：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dump = pre = ListNode(-1)
if not (head and head.next):
return head
while head and head.next:
temp1 = head
temp2 = head.next
temp1.next = temp2.next
temp2.next = temp1
pre.next = temp2
pre = temp1
head = temp1.next return dump.next
递归的实现代码如下：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
""" if not (head and head.next):
return head
new_head = head.next
head.next = self.swapPairs(head.next.next)
new_head.next=head
return new_head
coding交流群：226704167，郑州程序员群：59236263愿和各位一起进步！
微信公众号：欢迎关注