鏈表基礎(chǔ)知識(shí):

鏈表的定義：

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

移除鏈表元素

題目描述：

代碼編寫：

class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        dummy_head = ListNode(next=head)
        cur = dummy_head
        while cur.next != None:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy_head.next

反轉(zhuǎn)鏈表

題目描述：

代碼編寫：
要注意變量的命名，清晰的命名可以幫助題目的編寫土童。

class Solution(object):
    def reverseList(self, head):
        front = None
        cur = head
        while cur != None:
            rear = cur.next
            cur.next = front
            front = cur
            cur = rear
        return front

設(shè)計(jì)鏈表

題目描述：

代碼：

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

class MyLinkedList(object):

    def __init__(self):
        self.head = None
        self.size = 0

    def get(self, index):
        """
        :type index: int
        :rtype: int
        """
        if index < 0 or index >= self.size :
            return -1
        curr = self.head
        for _ in range(index):
            curr = curr.next
        return curr.val

    def addAtHead(self, val):
        """
        :type val: int
        :rtype: None
        """
        self.addAtIndex(0,val)

    def addAtTail(self, val):
        """
        :type val: int
        :rtype: None
        """
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index, val):
        """
        :type index: int
        :type val: int
        :rtype: None
        """
        if index > self.size or index < 0:
            return
        dummy = Node(-1)
        dummy.next = self.head
        prev = dummy
        new_node = Node(val)
        
        for _ in range(index):
            self.head = self.head.next
            prev = prev.next
            
        prev.next = new_node
        new_node.next = self.head
        self.head = dummy.next
        self.size += 1
            
    def deleteAtIndex(self, index):
        """
        :type index: int
        :rtype: None
        """
        if index < 0 or index >= self.size:
            return 
        
        dummy = Node(-1)
        dummy.next = self.head
        prev = dummy
        
        for _ in range(index):
            self.head = self.head.next
            prev = prev.next
            
        prev.next = self.head.next
        self.head = dummy.next
        self.size -= 1