Fork me on GitHub

LeetCode-链表

发表于 | 分类于
字数统计: 1.1k
慢慢刷，希望坚持下来。

链表排序

节点类

1
2
3
4
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        
        if not head or not head.next: return head
#         使用一个辅助节点指向头结点
        pstart = ListNode(-1)
        pstart.next = head
        pend = head
        p = head.next
        
        while p:
            temp = pstart.next
            pre = pstart
#             找到待插入的位置，需要保留两个节点地址
            while temp != p and temp.val<p.val:
                pre = temp
                temp = temp.next
            if temp == p:pend = p
            else:
                pend.next = p.next
                p.next = temp
                pre.next = p
            p = pend.next
        head = pstart.next
        return head

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def selectionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        
        if not head or not head.next: return head
#         使用一个辅助节点指向头结点
        pstart = ListNode(-1)
        pstart.next = head
        pend = pstart
        
        while pend.next:
            p,min_p = pend.next,pend.next
            while p:
                if p.val<min_p.val:
                    min_p = p
                p = p.next
            pend.next.val,min_p.val = min_p.val,pend.next.val
            pend = pend.next
        head = pstart.next
        
        return head

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def bubbleSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        
        if not head or not head.next: return head
        p = None
        is_change = True
        while p != head.next and is_change:
            q = head
            is_change = False
            while q.next and q.next != p:
                if q.val > q.next.val:
                    q.val,q.next.val = q.next.val,q.val
                    is_change = True
                q = q.next
            p = q
        return head

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:return head
        self.quick_sort_list(head,None)
        return head
        
    def quick_sort_list(self,head,tail):
        if head != tail and head.next != tail:
            m = self.partition(head,tail)
            self.quick_sort_list(head,m)
            self.quick_sort_list(m.next,tail)
            
    def partition(self,p,r):
        pivot = p
        q = p
        p = p.next
        while p != r:
            if p.val<pivot.val:
                q = q.next
                q.val,p.val = p.val,q.val
                
            p = p.next
        pivot.val,q.val = q.val,pivot.val
        return q

LeetCode23 合并K个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        K = len(lists)
        if K == 0:
            return None
        while K>1:
            n = (K+1)>>1
            for i in range(K>>1):
                lists[i] = self.merge_two_list(lists[i],lists[i+n])
            K = n
        return lists[0]
    def merge_two_list(self,l1,l2):
        head = ListNode(0)
        cur = head
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        if l1:
            cur.next = l1
        if l2:
            cur.next = l2
        return head.next

LeetCode82 删除排序链表中的重复元素

类似与集合操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return head
        pre = head
        cur = head.next
        while cur:
            if pre.val == cur.val:
                
                cur = cur.next
                continue
            pre.next = cur
            pre = pre.next
            cur = cur.next
        pre.next = cur
        return head

LeetCode83 删除排序链表中的重复元素II

只要有重复的，重复的都要删除，不保留

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return head
        h = ListNode(-1)
        h.next = head
        pre = h
        cur = head
        
        while cur:
            du = False
            while cur.next and cur.next.val == cur.val:
                du = True
                cur = cur.next
            if du:
                cur = cur.next
                continue
            pre.next = cur
            pre = pre.next
            cur = cur.next
        pre.next = cur
        return h.next

LeetCode138. 复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深度拷贝。

分三步进行：

  1. 生成每个节点的复制，并将其插入后面
  2. 再次遍历新的链表，若当前节点有随机指针，那么复制节点的随机指针为当前节点随机指针指向节点的下一个节点
  3. 断开
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if not head:return None
        p = head
        while p:
            temp = RandomListNode(p.label)
            temp.next = p.next
            p.next = temp
            p = temp.next
        p1,p2 = head,head.next
        while p1:
            if p1.random:
                p2.random = p1.random.next
            
            p1 = p2.next
            if p1:
                p2 = p1.next
            
        p1,p2 = head,head.next
        res = head.next
        while p1:
            p1.next = p2.next
            if p1:
                p1 = p1.next
            if p1:
                p2.next = p1.next
                p2 = p2.next
        return res

LeetCode141. 环形链表

给定一个链表，判断链表中是否有环。
快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head: return False
        p1,p2 = head,head
        while p2 and p1:
            if p2.next is None: return False
            p2 = p2.next.next
            p1 = p1.next
            if p1 == p2:
                return True
        return False

LeetCode142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None: return None
        
        p1,p2 = head,head
        
        while p1 and p2:
            if p2.next is None: return None
            if p2.next.next is None: return None
            
            p2 = p2.next.next
            p1 = p1.next
            
            if p1 == p2:
                break
        length = 1
        p2 = p2.next
        while p1 != p2:
            p2 = p2.next
            length += 1
            
        p1,p2 = head,head
        i = 0
        while i < length:
            p2 = p2.next
            i += 1
        while p1 != p2:
            p1 = p1.next
            p2 = p2.next
        return p1
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多