leetcode/LinkedListInsertionSort.py at master · tnstar/leetcode · GitHub

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
'''
Created on Mar 17, 2014

@author: C_TLU
'''


#Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def __init__(self):
        self.phead = None
    def insert_node_tail (self,pcur,pnext):
        pcur.next = pnext
        pnext.next = None
    def insert_node_2 (self,pprev,pcur):
        ppnext = pprev.next
        pprev.next = pcur
        pcur.next = ppnext
    def find_node_pos(self,phead,pnode):
        pcur = phead
        while pcur:
            pnext = pcur.next
            if pnext == None:
                break

            if pcur == phead:
                if pnode.val <= pcur.val:
                    #this means should append before the phead
                    pcur.next = phead
                    phead = pcur
                    self.phead = phead
            else:
                if pnode.val<= pnext.val and pnode.val >=pcur.val:
                    self.insert_node_2(pcur, pnext)
                    break
            pcur = pcur.next
    def insertionSortList(self, head):
        self.phead = head
        phead = head
        pmax = head # pmax means the maxium position in the assertion array
        pcur = head # pcur is the dynamic pointer for the insertion point
        pnext = pcur.next # pnext means next testing node

        while pnext:
            if pnext.val > pmax.val:
                pcur = pmax # moving pointer to pmax
                pcur.next = pnext # set next node to pmax.next
                pnext = pnext.next
                if pnext:
                    pnext.next = None
            else:
                temp = pnext.next
                self.find_node_pos(phead,pnext)
                phead = self.phead
                pnext = temp
        return phead
h1 = ListNode(4)
h1.next = ListNode(3)
h1.next.next = ListNode(6)
h1.next.next.next = ListNode(5)
sol = Solution()
test = sol.insertionSortList(h1)
raw_input()