众所周知，计算机中的数据结构底层无非是链表（linked list）或者线性表（linear list）。因此，掌握这些基本的数据结构的结构和常用操作是很重要的。本文我们来介绍一下链表的常用操作，主要采用经典算法题的形式来加以呈现说明
0. 链表的数据结构描述
略
1. 常见操作
1.1 删除链表中的结点
leetcode-237 237. 删除链表中的节点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
node.val=node.next.val
node.next=node.next.next
关键点：将该节点后继节点的数据拷贝到当前节点，并且删除后继节点
1.2 合并有序链表
leetcode-21 21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if l1 is None:
return l2
if l2 is None:
return l1
start=None
cur=None
if l2.val <= l1.val:
cur=l2
l2=l2.next
else:
cur=l1
l1=l1.next
start=cur
while l1 is not None and l2 is not None:
if l2.val <= l1.val:
cur.next=l2
l2=l2.next
else:
cur.next=l1
l1=l1.next
cur=cur.next
if l1 is not None:
cur.next=l1
else:
cur.next=l2
return start
关键点：l1和l2分别往后逐节点移动并比较大小，利用一个指针cur来指向l1和l2中较小的节点，并将cur往后移动。当l1或l2有一个为None时，迭代停止， 不为空的那个节点开始的尾巴直接连在cur后面。要注意的是，需要一个start节点来指向起点。
1.3. 反转链表
leetcode-206 206. 反转链表
给你单链表的头节点?head?，请你反转链表，并返回反转后的链表。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head is None:
return head
p1=head
p2=head.next
while p2 is not None:
head.next=p2.next
p2.next=p1
p1=p2
p2=head.next
return p1
关键点：用两个指针p1和p2，一前一后，每次迭代时head指向p2的后继结点，p2指向p1，p1移动到p2，p2移动到下一个节点（借助head）。
|