python算法技巧——链表练习及掌握

目录

1. 建立链表：

2. 将链表数据反转：

3. 删除链表的节点：

 4. 合并两个排序好的链表：

5. 删除重复链表元素

6. 判断链表内容是不是回文：

7. 二进制链表改成整数：

---

1. 建立链表：

建立链表的模板代码：

class listnode():
    def __init__(self, x):
        self.val = x
        self.next = None

def create_link_list(nums):
    ptr_head = listnode(nums[0])
    ptr = ptr_head
    for x in range(1, len(nums)):
        n = listnode(nums[x])
        ptr.next = n
        ptr = ptr.next
    return ptr_head

data = create_link_list([1,2,3,4,5])
reverselist(data)
while data:
    print(data.val)
    data = data.next

2. 将链表数据反转：

代码如下:

class listnode():
    def __init__(self, x):
        self.val = x
        self.next = None

def create_link_list(nums):
    ptr_head = listnode(nums[0])
    ptr = ptr_head
    for x in range(1, len(nums)):
        n = listnode(nums[x])
        ptr.next = n
        ptr = ptr.next
    return ptr_head

def reverselist(head):
    ptr = head
    mylist = []
    while ptr:
        mylist.insert(0, ptr.val)
        ptr = ptr.next
    ptr = head
    for data in mylist:
        ptr.val = data
        ptr = ptr.next
    return head

data = create_link_list([1,2,3,4,5])
reverselist(data)
while data:
    print(data.val)
    data = data.next

3. 删除链表的节点：

代码如下:

class listnode():
    def __init__(self, x):
        self.val = x
        self.next = None

def create_link_list(nums):
    ptr_head = listnode(nums[0])
    ptr = ptr_head
    for x in range(1, len(nums)):
        n = listnode(nums[x])
        ptr.next = n
        ptr = ptr.next
    return ptr_head

def removeelements(head, val):
    new_ptr = ptr = listnode(0)
    ptr.next = head
    while head:
        if head.val == val:
            ptr.next = head.next
        else:
            ptr = ptr.next
        head = head.next
    return new_ptr.next

data = create_link_list([1,2,3,4,5,3])
removeelements(data, 3)
while data:
    print(data.val)
    data = data.next

 4. 合并两个排序好的链表：

代码如下： 

class listnode():
    def __init__(self, x):
        self.val = x
        self.next = None

def create_link_list(nums):
    ptr_head = listnode(nums[0])
    ptr = ptr_head
    for x in range(1, len(nums)):
        n = listnode(nums[x])
        ptr.next = n
        ptr = ptr.next
    return ptr_head

def  mergetwolists(list1, list2):
    if not list1 or not list2:
        return list1 or list2
    new_ptr = ptr = listnode(0)
    while list1 and list2:
        if list1.val > list2.val:
            ptr.next = list2
            list2 = list2.next
        else:
            ptr.next = list1
            list1 = list1.next
        ptr = ptr.next
    ptr.next = list1 or list2
    return new_ptr.next

data1 = create_link_list([1,3,5])
data2 = create_link_list([1,2,6])
data = mergetwolists(data1, data2)
while data:
    print(data.val)
    data = data.next

5. 删除重复链表元素

代码如下： 

class listnode():
    def __init__(self, x):
        self.val = x
        self.next = None

def create_link_list(nums):
    ptr_head = listnode(nums[0])
    ptr = ptr_head
    for x in range(1, len(nums)):
        n = listnode(nums[x])
        ptr.next = n
        ptr = ptr.next
    return ptr_head

def deleteduplicates(head):
    ptr = head
    while ptr:
        if ptr.next and ptr.next.val == ptr.val:
            ptr.next = ptr.next.next
        else:
            ptr = ptr.next
    return ptr

data = create_link_list([1,1,2,3,3,3,4,4,5])
deleteduplicates(data)
while data:
    print(data.val)
    data = data.next

6. 判断链表内容是不是回文：

 代码如下： 

class listnode():
    def __init__(self, x):
        self.val = x
        self.next = None

def create_link_list(nums):
    ptr_head = listnode(nums[0])
    ptr = ptr_head
    for x in range(1, len(nums)):
        n = listnode(nums[x])
        ptr.next = n
        ptr = ptr.next
    return ptr_head

def ispalindrome(head):
    mylist = []
    while head:
        mylist.append(head.val)
        head = head.next
    length = len(mylist)
    for i in range(int(length/2)):
        if mylist[i] != mylist[length-i-1]:
            return False
    return True

data1 = create_link_list([1,1,2,3,3,3,4,4,5])
data2 = create_link_list([1,1,2,3,3,3,2,1,1])
print(ispalindrome(data1))
print(ispalindrome(data2))

7. 二进制链表改成整数：

  代码如下： 

class listnode():
    def __init__(self, x):
        self.val = x
        self.next = None

def create_link_list(nums):
    ptr_head = listnode(nums[0])
    ptr = ptr_head
    for x in range(1, len(nums)):
        n = listnode(nums[x])
        ptr.next = n
        ptr = ptr.next
    return ptr_head

def getdecimalvalue(head):
    value = 0
    while head:
        value = value*2 + head.val
        head = head.next
    return value

print(getdecimalvalue(create_link_list([0,1])))
print(getdecimalvalue(create_link_list([1,1])))
print(getdecimalvalue(create_link_list([1,0,1])))