首页 > > 网络编程 > 其它 >

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

2018-06-18 02:18:57来源：未知阅读 ()

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

微信公众号：欢迎关注