鏈表

鏈表中每一個節點為一個對象，對象中包含兩個成員變量，第一個是val，代表鏈表的值，第二個是next，它指向下一個節點，是下一個節點對象的引用。

定義鏈表

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

刪除節點

給定鏈表中的某個節點，刪除該節點

class Solution {public void deleteNode(ListNode node) {node.val = node.next.val;node.next = node.next.next;}
}

反轉鏈表

普通方法：

def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:newHead = Nonewhile head != None:temp = head.nexthead.next = newHeadnewHead = headhead = tempreturn newHead

使用棧解決:
一定要注意讓尾巴節點next指針為空，否則將形成環：

def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:if head == None:return Nonea = []while head != None:a.append(head)head = head.nexthead = a.pop()b = headwhile len(a) > 0:n = a.pop()b.next = nb = nb.next = Nonereturn head

合并兩個有序鏈表

合并兩個升序鏈表，變成一個新的升序鏈表

遞歸：

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:if list1 is None: return list2if list2 is None: return list1if list1.val <= list2.val:list1.next = self.mergeTwoLists(list1.next, list2)return list1else:list2.next = self.mergeTwoLists(list1,list2.next)return list2

判斷鏈表是否有環

直觀解法：

class Solution:def hasCycle(self, head: Optional[ListNode]) -> bool:a = []while head != None:if head not in a:a.append(head)head = head.nextelse:return Truereturn False

快慢指針：

class Solution:def hasCycle(self, head: Optional[ListNode]) -> bool:head1 = headhead2 = headwhile head1 != None and head2 != None and head2.next != None:head1 = head1.nexthead2 = head2.next.nextif head1 == head2:return Truereturn False