如何在Python中创建与使用链表（单链表）

---

最近用Python语言在Leetcode中刷题，接触到不少关于链表的题，学校目前还没有开设数据结构的课程（开设的话应该也是以C/C++语言写的）。

因为不太了解链表使用方式，开始跳过了这些题，不过后来还是自己研究了一下，大概是了解了，看到评论区也有人不知道链表的使用方式，就打算总结一下。

首先来看一下Leetcode官方定义的链表：

# Definition for singly-linked list.
class ListNode(object):def __init__(self, val=0, next=None):self.val = valself.next = next

第一行说明了这是对单链表的定义。
其中链表元素只有两个属性，即val和next，前者代表当前原色的值，后者代表着这个元素指向的下一元素。next=None说明next的默认指向None。

创建一个链表

可以使用如下方式：

head = None
for i in [4,3,2,1,0]:head = ListNode(i,head)

首先让表头（最终会是最后一个元素）指向None，然后利用for循环依次添加这个链结的前一个元素。因此，最终获得的链表会是这样的：

遍历一个链表

value = []
head2 = head
while head:value.append(head2.val)head2 = head2.next

这里使用一个列表来保存链表中元素的值。
在每次获取head的值之后，向前移一位。
由于是单链表,所以通过定义head2来保留链表的头部。
否则，while循环遍历后将无法访问链表的元素。

几道使用到链表的Leetcode题解

• 两数之和 （简单）
  给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。 请你将两个数相加，并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

class Solution(object):def addTwoNumbers(self, l1, l2):num1 = 0num2 = 0times = 0while l1 != None or l2 != None:if l1 != None:num1 += 10**times*l1.vall1 = l1.nextif l2 != None:num2 += 10 ** times * l2.vall2 = l2.nexttimes += 1num3 = num1 + num2temp = ListNode(0)head = tempfor i in reversed(str(num3)):temp.next = ListNode(int(i))temp = temp.nextreturn head.next

• 删除链表的倒数第N个结点 （中等）
  给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。

class Solution(object):def removeNthFromEnd(self, head, n):length = 0t = headx = headwhile head:length += 1head = head.nextcurrent = 1while t:if current == length - n and n != 1 and n != length:t.next = t.next.nextelif n == 1 and current == length - 1 :t.next = Nonereturn xelif n == length:return t.nextt = t.nextcurrent += 1return x

• 合并两个有序链表 （简单）
  将两个升序链表合并为一个新的升序链表并返回。 新链表是通过拼接给定的两个链表的所有节点组成的。

class Solution(object):def mergeTwoLists(self, list1, list2):if not list1:return list2if not list2:return list1result = Nonewhile list1 or list2:if not (list1 and list2):while list1:result = ListNode(list1.val,result)list1 = list1.nextwhile list2:result = ListNode(list2.val,result)list2 = list2.nextelse:if list1.val < list2.val:result = ListNode(list1.val,result)list1 = list1.nextelse:result = ListNode(list2.val, result)list2 = list2.nextresult2 = Nonewhile result:result2 = ListNode(result.val,result2)result = result.nextreturn result2

• 两两交换链表中的节点 (中等)
  给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。 你必须在不修改节点内部的值的情况下完成本题 （即，只能进行节点交换）。

class Solution(object):def swapPairs(self, head):if not head:return headif not head.next:return headcopyhead = head.nextwhile head and head.next:second = head.nextif head.next.next:third = head.next.nextif head.next.next.next:head.next = head.next.next.nextelse:head.next = head.next.nextelse:head.next = Nonethird = Nonesecond.next = headhead = thirdreturn copyhead

• 删除排序链表中的重复元素（简单）
  给定一个已排序的链表的头head，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表 。

class Solution(object):def deleteDuplicates(self, head):node = headif not head:return headwhile head.next:if not head.next == None:if head.val == head.next.val:head.next = head.next.nextelse:head = head.nextreturn node

题目来源：力扣
查看原题：力扣题库