数据结构与算法 —— 链表linked list(03)

继续关于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愿和各位一起进步!

微信公众号:数据结构与算法 —— 链表linked list(03)欢迎关注

上一篇:sqlalchemy 的 ORM 方式使用示例


下一篇:Codeforces 1092E Minimal Diameter Forest