python 链表结构练习

class Node(object):
    __slots__ = ['val', 'next']

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

class SingleLinkedList(object):
    """单向链表结构实现"""
    def __init__(self):
        self._head = None  # 第一个元素指针
        self._last = None  # 最后一个元素指针
        self._size = 0

    def __str__(self):
        """完整的打印链表结构"""
        arr = []
        current = self._head
        while current is not None:
            arr.append(str(current.val))
            current = current.next
        return "{0}({1})".format(__class__, "=>".join(arr))

    def __len__(self):
        """返回链表大小"""
        return self._size

    def is_empty(self):
        """链表是否为空"""
        return self._head is None

    def append(self, val):
        """链表末尾增加元素"""
        node = Node(val)
        if self.is_empty():
            self._head = node
            self._last = node
        else:
            self._last.next = node
            self._last = node
        self._size += 1

    def add(self, val):
        """链表首部增加元素"""
        node = Node(val)
        if self.is_empty():
            self._head = node
            self._last = node
        else:
            node.next = self._head
            self._head = node
        self._size += 1

    def insert(self, pos, val):
        """固定位置插入元素"""
        node = Node(val)
        if pos <= 0:
            self.add(val)
        elif pos >= self._size:
            self.append(val)
        else:
            count = 1
            pre = self._head
            current = self._head.next
            while current is not None:
                if count == pos:
                    pre.next = node
                    node.next = current
                else:
                    current = current.next
                count += 1
        self._size += 1

    def index(self, val):
        """返回某个值的索引，未找到返回-1"""
        index = 0
        current = self._head
        while current is not None:
            if current.val == val:
                return index
            else:
                current = current.next
            index += 1
        return -1

    def get(self, index):
        """根据索引返回节点"""
        count = 0
        current = self._head
        if index < 0 or index >= self._size:
            raise Exception("IndexError: list index out of range")
        while current is not None:
            if count == index:
                return current
            else:
                current = current.next
            count += 1

    def remove(self, val):
        """删除某个值"""
        index = 0
        pre = None
        current = self._head
        while current is not None:
            if current.val == val:
                if pre is None:
                    self._head = self._head.next
                else:
                    pre.next = current.next
                self._size -= 1
                return
            else:
                pre = current
                current = current.next
            index += 1
        raise Exception("ValueError: remove(x): x not in list")

    def clear(self):
        """清空链表"""
        self._head = None
        self._size = 0
        self._last = None

    def pop(self, pos):
        """根据索引删除元素并返回"""
        count = 0
        pre = None
        current = self._head
        if pos < 0 or pos >= self._size:
            raise Exception("IndexError: pop index out of range")
        while current is not None:
            if count == pos:
                if pre is None:
                    self._head = self._head.next
                else:
                    pre.next = current.next
                self._size -= 1
                return current
            else:
                pre = current
                current = current.next
            count += 1

    def reverse(self):
        """反转链表结构"""
        if self._size <= 1:
            return self
        pre = self._head
        current = self._head.next
        pre.next = None
        self._last = pre
        while current is not None:
            next_node = current.next
            if next_node is None:
                # 到最后了，末尾元素变第一
                self._head = current
                print(self)
            current.next = pre
            pre = current
            current = next_node


if __name__ == '__main__':
    s = SingleLinkedList()
    print(s.is_empty())
    for i in range(10):
        s.append(i)
    print("append 1~10", s)
    print("size: ", len(s))
    print("index(3)", s.index(3))
    # print("index(13)", s.index(13))
    print("get(3)", s.get(3), s.get(3).val)
    # print("get(13)", s.get(13))
    print("pop(9)", s.pop(9).val, s)
    print("pop(5)", s.pop(5).val, s)
    print("size: ", len(s))
    print("remove(6)", s.remove(6), s)
    print("remove(0)", s.remove(0), s)
    print("size: ", len(s))
    print("s.reverse()", s.reverse(), s)
    s.add(-1)
    print("add(-1)", s)
    s.add(-2)
    print("add(-2)", s)
    s.append(0)
    print("append(0)", s)
    print("size: ", len(s))
    s1 = SingleLinkedList()
    print("s1: ", s1)
    s1.insert(1, 1)
    print("insert(1,1)", s1)
    s1.insert(2, 2)
    print("insert(2,2)", s1)
    s1.insert(1, 3)
    print("insert(1,3)", s1)
    s1.insert(0, 4)
    print("insert(1,3)", s1)

链表结构练习题：

https://leetcode-cn.com/problems/add-two-numbers/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = result = ListNode(0)
        t = 0
        while l1 is not None or l2 is not None:
            if l1 is not None:
                t += l1.val
                l1 = l1.next
            if l2 is not None:
                t += l2.val
                l2 = l2.next
            result.next = ListNode(t % 10)
            result = result.next
            t = t // 10
        # 最后一位的时候如果大于0需要进1
        if t > 0:
            result.next = ListNode(t)
        return head.next

if __name__=='__main__':
    s = Solution()
    l1 = ListNode(3)
    l2 = ListNode(4, next=l1)
    l3 = ListNode(2, next=l2)
    l4 = ListNode(4)
    l5 = ListNode(6, next=l4)
    l6 = ListNode(5, next=l5)
    L1 = l3
    L2 = l6
    r = s.addTwoNumbers(L1, L2)
    c = r

    while c is not None:
        print(c.val, end='')
        c = c.next