链表

全文概览

如果须要本文的PDF文档，请分割作者。或者关注公众【程序员学长】获取。

链表基础知识

链表的分类

链表是一种通过指针串联在一起的线性构造，次要分为单链表、双向链表和循环链表。

单链表

单链表中每一个节点是由两局部组成，一个是数据域、一个是指针域（寄存指向下一个节点的指针），最初一个节点的指针域为空。

双向链表

双向链表中的每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。双向链表既能够向前查问也能够向后查问。

单向循环链表

单向循环链表是指首尾相连的单链表。

双向循环链表

双向循环链表是指首尾相连的双向链表。

链表的定义

咱们在刷LeetCode的时候，因为链表的节点都默认定义好了，间接用就行了，然而在面试的时候，一旦要手写链表代码时，节点的定义是大家容易犯错的中央，所有咱们来看一下定义链表节点的形式。

#单链表class ListNode(object):    def __init__(self, x):        #数据域        self.val = x        #指针域        self.next = None

链表的操作

单链表的删除操作

删除链表中的q节点，只须要执行p->next=q->next，即让p的指针域指向q的下一个节点。

向单链表中减少一个节点

在节点p后减少一个节点q，只须要执行q->next=p->next，p->next=q即可，这里肯定要留神执行的先后顺序。如果先执行p->next=q，那么原链表的p->next的信息就失落了。

解题有妙招

引入哑结点

哑结点也叫做哨兵节点，对于链表相干的题目，为了不便解决边界条件，个别咱们都会引入哑结点来不便求解。首先咱们来看一下什么是哑结点，哑结点是指数据域为空，指针域指向链表头节点的节点，它是为了简化边界条件而引入的。上面咱们来看一个具体的例子，例如要删除链表中的某个节点操作。常见的删除链表的操作是找到要删元素的前一个元素，如果咱们记为 pre。咱们通过：pre->next=pre->next->next来执行删除操作。如果此时要删除的是链表的第一个结点呢？就不能执行这个操作了，因为链表的第一个结点的前一个节点不存在，为空。如果此时你设置了哑结点，那么第一个结点的前一个节点就是这个哑结点。这样如果你要删除链表中的任何一个节点，都能够通过pre->next=pre->next->next的形式来进行，这就简化的代码的逻辑。

双指针法

在求解链表相干的题目时，双指针也是十分罕用的思维，例如对于求解链表有环问题时，咱们申请两个指针，以一快一慢的速度在链表上行走，等他们相遇时，就能够晓得链表是否有环；或者在求链表的倒数k个节点时，申请两个指针，一个指针先走k步，而后两个指针再同时向后挪动，当先走的那个指针走到链表的开端时，另一个指针恰好指向了倒数第k个节点。

反转链表

LeetCode206. 反转链表

问题形容

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。示例:输出：head = [1,2,3,4,5]输入：[5,4,3,2,1]

剖析问题

首先，咱们依照题目的要求，先把图画进去，而后再剖析。

从图中咱们能够看到，反转前和反转后指针的指向产生了反转。所以，咱们在实现的过程中，咱们能够通过调整链表的指针来达到反转链表的目标。

咱们定义两个指针pre和cur。pre示意已反转局部的头结点，cur示意还没有反转局部的头结点。开始时cur=head，pre=None
每次让cur->next=pre，实现一次部分反转。
部分反转实现后，cur和pre同时向前挪动一位。
循环上述过程，直到链表反转实现。

代码实现

class ListNode:    def __init__(self, val=0, next=None):        self.val = val        self.next = nextclass Solution:    def reverse(self, head):        cur = head        #初始化时，pre为None        pre = None        while cur:            next=cur.next            cur.next = pre            pre = cur            cur = next        return prehead=ListNode(1,None)cur=headfor i in range(2,6):    tmp=ListNode(i,None)    cur.next=tmp    cur=cur.nexts=Solution()pre=s.reverse(head)while pre!=None:    print(pre.val)    pre=pre.next

合并两个有序链表

LeetCode21. 合并两个有序链表

问题形容

输出两个枯燥递增的链表，输入两个链表合成后的链表，咱们须要合成后的链表满足枯燥不减规定。

示例：

输出: {1,3,5},{2,4,6}

返回值: {1,2,3,4,5,6}

剖析问题

既然给定的两个链表都是有序的，那么咱们能够判断两个链表的头结点的值的大小，将较小值的结点增加到后果中，而后将对应链表的结点指针后移一位，周而复始，直到有一个链表为空为止。

因为链表是有序的，所以循环终止时，那个非空的链表中的元素都比后面曾经合并的链表中的元素大，所以，咱们只须要简略地将非空链表接在合并链表的前面，并返回合并链表即可。

首先咱们须要先创立一个哨兵节点，而后将prehead指向链表l1和l2中比拟小的一个。如果相等的话，指向任意一个即可。而后将较小值对应的链表的指针后移一位。

咱们上面来看一下代码实现。

def mergeTwoLists(self, l1, l2):        #合并后链表的哨兵结点        head=ListNode(-1,None)        pre=head        #循环遍历，将两个链表中的较小值插入到合并后的链表中        while l1 and l2:            if l1.val <= l2.val:                pre.next=l1                l1=l1.next            else:                pre.next=l2                l2=l2.next            pre=pre.next        #将残余的非空链表插入到合并链表的前面        if l1:            pre.next=l1        else:            pre.next=l2        return head.next

其实，咱们这里也能够应用递归的形式来实现。

class ListNode:    def __init__(self, val=0, next=None):        self.val = val        self.next = nextclass Solution:    def mergeTwoLists(self, l1, l2):        #链表l1为空，不须要合并，间接返回l2        if(l1==None):            return l2        #同理，l2为空，间接返回l1即可            if(l2==None):            return l1        if(l1.val<=l2.val):            l1.next=self.mergeTwoLists(l1.next,l2)            return l1        else:            l2.next=self.mergeTwoLists(l1,l2.next)            return l2

问题降级

LeetCode23. 合并K个升序链表

上面，咱们来把问题降级一下，将两个有序链表合并改成多个有序链表合并，咱们来看一下题目。

给定一个有序链表，其中每个节点也示意有一个有序链表。结点蕴含两个类型的指针：

指向主链表中下一个结点的指针。
指向以此结点为头的链表。

示例如下所示：

  4 ->  9 -> 15 -> 19  |     |     |     |  7    13    18    28  |           |     |  8          21    37  |                  20                  实现函数flatten()，该函数用来将链表扁平化成单个链表。例如下面的链表，输入链表为   4 -> 7 -> 8 -> 9 -> 13 -> 15 -> 18 ->19 -> 20 -> 21 -> 28 -> 37

题目要求咱们把二维有序链表合并成一个单链表，咱们来把问题简化一下，假如主链表只有两个节点，即这个二维链表变成如下所示。

 4 ->  9   |     |       7    13           旋转一下         4 -> 7 -> 8 -> 20  |               ---------->       |  8                                 9 -> 13  |                  20

这不就是咱们下面讲的两个有序链表合并吗？那如果主链表有多个节点呢？咱们能够应用归并的思维，一一去合并就好了，如下图所示。

上面咱们来看一下代码如何实现。

class ListNode:    def __init__(self, val=0, right=None, down=None):        self.val = val        self.right = right        self.down = downclass Solution:    def mergeTwoLists(self, l1, l2):        #如果有一个链表为空，则合并后的链表就是另外一个        if(l1==None):            return l2        if(l2==None):            return l1        if(l1.val<=l2.val):            l1.down=self.mergeTwoLists(l1.down,l2)            return l1        else:            l2.down=self.mergeTwoLists(l1,l2.down)            return l2    def flatten(self,root):        if root== None or root.right == None:            return root        #把root->right 看作是曾经有序的单链表，        #而后通过递归来进行归并        return self.mergeTwoLists(root, self.flatten(root.right))

链表中的节点每k个一组翻转

问题形容

LeetCode25. K 个一组翻转链表

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表。如果链表中的节点数不是 k 的倍数，将最初剩下的节点放弃原样。你不能更改节点中的值，只能更改节点自身。

例如：

给定的链表是：1 -> 2 -> 3 -> 4 -> 5

对于 k=2，你应该返回 2 -> 1 -> 4 -> 3 -> 5

对于 k=3，你应该返回 3 -> 2 -> 1 -> 4 -> 5

剖析问题

咱们把这个问题进行拆分。

咱们首先将链表依照k个一组进行分组。对于最初一组，有可能元素个数不满足k个。
对于每一个分组，咱们去判断元素的个数是否为k，如果是k的话，咱们进行反转，否则不须要进行反转。

咱们上面来看一下代码实现。

class ListNode:    def __init__(self, val=0, next=None):        self.val = val        self.next = nextclass Solution:    #反转链表，并且返回链表头和尾    def reverse(self, head, tail):        prev = tail.next        p = head        while prev != tail:            next = p.next            p.next = prev            prev = p            p = next        return tail, head    def reverseKGroup(self, head, k):        #初始化一个哨兵节点，防止临界条件简单的判断        prehead = ListNode(0)        #哨兵节点指向头结点        prehead.next = head        pre = prehead        while head:            tail = pre            #查看残余局部长度是否大于等于k            for i in range(k):                tail = tail.next                #如果残余长度小于k,则不须要反转，间接返回                if not tail:                    return prehead.next            #tail指向子链表的尾部            #所以next指向下一个子链表的头部            next = tail.next            #将链表进行反转，并返回链表头和尾            head, tail = self.reverse(head, tail)            #把子链表从新接回原链表            pre.next = head            tail.next = next            pre = tail            head = tail.next                    return prehead.next

判断链表是否有环

问题形容

LeetCode141. 环形链表

给定一个链表，判断链表中是否有环。如果链表中有某个节点，能够通过间断跟踪 next 指针再次达到，则链表中存在环。为了示意给定链表中的环，咱们应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。留神：pos 不作为参数进行传递，仅仅是为了标识链表的理论状况。

如果链表中存在环，则返回 true 。否则，返回 false 。

示例：

输出：head = [-1,-7, 7,-4, 9, 6, -5, -2], pos = 3

输入：true

解释：链表中有一个环，其尾部连贯到第二个节点。

剖析问题

拿到这个问题，咱们最直观的想法就是在遍历结点的过程中去标记一下这个结点是否曾经被拜访过。如果被拜访过，那么就代表该链表有环，间接返回。如果没有被拜访过，咱们就标记一下，而后接着去遍历下一个结点，直到遍历残缺个链表为止。上面咱们来看一下代码的实现。

def hasCycle(self, head):    tags = set()    while head:        #示意曾经被拜访过了，代表有环        if head in tags:            return True        tags.add(head)        head = head.next    return False

咱们能够晓得该算法的工夫复杂度和空间复杂度都是O(n)。那咱们有更好的解法吗？

优化

你能够这么思考，当有两名同学在操场上以不同的速度进行跑步，它们最终必定会相遇。因为操场是环形的，如果在直线上跑，那他们必定不会相遇。

咱们假如同学1以速度1在跑，同学2以速度2在跑。

上面咱们来看一下代码如何实现。

def hasCycle(self, head):    #如果链表为空或者链表只有一个结点    #间接返回false,因为不可能有环    if not head or not head.next:        return False    #快慢指针    slow = fast = head    start = True    while slow != fast || start:        start=False        if not fast or not fast.next:            return False        slow = slow.next        fast = fast.next.next    return True

咱们这里引入了一个变量start示意是否是起跑。

能够看到该算法的空间复杂度升高为O(1)。

链表中环的入口结点

问题形容

LeetCode 剑指 Offer II 022. 链表中环的入口节点

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了示意给定链表中的环，咱们应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。留神，pos 仅仅是用于标识环的状况，并不会作为参数传递到函数中。

阐明：不容许批改给定的链表。

剖析问题

拿到这个问题，咱们最直观的想法就是在遍历结点的过程中去标记一下这个结点是否曾经被拜访过。如果被拜访过，就代表这个结点是链表中环的入口点，咱们间接返回就好。如果没有被拜访过，咱们就标记一下，而后接着去遍历下一个结点，直到遍历残缺个链表为止。上面咱们来看一下代码的实现。

def EntryNodeOfLoop(self, pHead):        tags = set()        while pHead:            #示意曾经被拜访过了，代表有环            if pHead in tags:                return pHead            tags.add(pHead)            pHead = pHead.next        return None

咱们能够看到该算法的工夫复杂度和空间复杂度都是O(n)。

优化

咱们这里也能够采纳快慢指针来求解，就和上一题的解法相似，咱们来看一下。

咱们能够应用两个指针fast和slow。他们都从链表的头部开始登程，slow每次都走一步，即slow=slow->next，而fast每次走两步，即fast=fast->next->next。如果链表中有环，则fast和slow最终会在环中相遇。

咱们假如链表中环外的长度为a，show指针进入环后又走了b的间隔与fast相遇，此时fast指针曾经绕着环走了n圈。所以快指针一共走了a+n(b+c)+b=a+(n+1)b+nc的间隔，咱们晓得快指针每次走2步，而慢指针每次走一步，所以，咱们能够得出快指针走的间隔是慢指针的两倍，即a+(n+1)b+nc=2(a+b)，所以a=c+(n-1)(b+c)。这里你会发现：从相遇点到入环的间隔c，再加上n-1圈的环长，恰好等于从链表头部到入环点的间隔。

因而，当发现slow和fast相遇时，咱们再额定应用一个指针ptr指向链表头部，而后它和slow指针每次都向后挪动一个地位。最终，他们会在入环点相遇。

Tips: 你兴许会有疑难，为什么慢指针在第一圈没走完就会和快指针相遇呢？咱们来看一下，首先，快指针会率先进入环内。而后，当慢指针达到环的入口时，快指针在环中的某个地位，咱们假如此时快指针和慢指针的间隔为x，若x=0，则示意在慢指针刚入环时就相遇了。咱们假如环的长度为n，如果看成快指针去追赶慢指针，那么快指针须要追赶的间隔为n-x。因为快指针每次都比慢指针多走一步，所以一共须要n-x次就能追上慢指针，在快指针遇上慢指针时，慢指针一共走了n-x步，其中x>=0，所以慢指针走的途程小于等于n，即走不完一圈就会相遇。

上面，咱们来看一下代码实现。

def detectCycle(head):    if not head:        return None    #快慢指针    slow = head    fast = head    while True:        if not fast or not fast.next:            return None        fast=fast.next.next        slow=slow.next        #相遇时，跳出循环        if fast == slow:            break    ptr = head    while ptr != slow:        ptr=ptr.next        slow=slow.next    return ptr

该算法的工夫复杂度是O(n)，空间复杂度是O(1)。

删除链表倒数第n个节点

问题形容

LeetCode 剑指 Offer II 021. 删除链表的倒数第 n 个结点

给定一个链表，删除链表的倒数第 n个结点，并且返回链表的头结点。

示例：

输出：head = [1,2,3,4,5], n = 2

输入：[1,2,3,5]

剖析问题

这个问题最简略的求解形式就是遍历一遍链表，获取到链表的长度m，而后求出倒数第n个结点的地位m-n+1，而后再遍历一次链表，找到第m-n+1的地位，删掉这个结点就好。其实，咱们这里能够应用双指针法，只须要遍历一次链表就能够解决问题。

首先，咱们能够设置两个指针slow和fast都指向头结点，而后让fast先走n步，之后slow和fast一起走，直到fast.next为空为止，这是slow指向的就是倒数第n+1个结点，咱们通过slow.next=slow.next.next就能够把倒数第n个结点删掉。

上面咱们来看一下代码的实现。

    def removeNthFromEnd(self,head,n):            #左右指针指向头结点        slow = fast = head        #fast先走n步        while n>0 and fast:            fast = fast.next            n=n-1                    if not fast:            return head.next                while fast.next:            slow = slow.next            fast = fast.next        slow.next = slow.next.next        return head

该算法只遍历一遍链表，所以工夫复杂度是O(n)，空间复杂度是O(1)。

两个链表的第一个公共结点

问题形容

LeetCode 剑指 Offer 52. 两个链表的第一个公共节点

输出两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。

要求：空间复杂度是O(1)，工夫复杂度是O(m+n)。

示例：

剖析问题

这个问题最直观的想法就是遍历链表headA，而后把headA中的所有每个节点都退出到汇合中。而后再循环遍历链表headB，判断结点是否在汇合中，如果在，则返回该结点，该结点就代表第一个公共结点。如果不在，持续遍历，直到完结。如果headB的所有结点都不在汇合中，则表明不相交，间接返回null。

def getIntersectionNode(headA,headB):    nodes=set()    while headA:        nodes.add(headA)        headA=headA.next    while headB:        if nodes.__contains__(headB):            return headB        headB=headB.next    return None

该算法的工夫复杂度是O(m+n)，空间复杂度是O(n)。其中m和n别离是链表headA和headB的长度。

因为题目要求工夫复杂度是O(m+n)，空间复杂度是O(1)。咱们这里能够应用双指针法将空间复杂度升高到O(1)。咱们别离用两个指针p1和p2别离指向headA和headB，而后同时挪动指针p1和p2。当p1达到headA的开端时，让p1指向headB，当p2达到headB的开端时，让p2指向headA，这样，当它们相遇时，所指的节点就是第一个公共结点。

Tips:假如headA不相交的局部是a，headB不相交的局部是b，公共局部是c，那么headA的长度为a+c，headB的长度为b+c，当a等于b时，能够晓得p1和p2指针同时达到第一个公共结点；当a不等于b时，在p1挪动了a+b+c时，即p1走完headA，又在headB上走了b时，p2也走了a+b+c，即p2走完headB，而后又在headA上走了a，此时p1和p2正好相遇，且指向了第一个公共结点。

def getIntersectionNode(headA,headB):    p1 = headA    p2 = headB    while p1 != p2:        if p1:            p1=p1.next        else:            p1=headB        if p2:            p2=p2.next        else:            p2=headA    return p1

两个链表生成相加链表

问题形容

LeetCode 剑指 Offer II 025. 链表中的两数相加

假如链表中每一个节点的值都在 0 - 9 之间，那么链表整体就能够代表一个整数。给定两个这种链表，请生成代表两个整数相加值的后果链表。

示例：

输出：[9,3,7]，[6,3]

返回值：{1,0,0,0}

剖析问题

因为两个数字相加是从个位数开始，而后再十位数、百位数。对于的链表中，咱们须要将两个链表进行右端对齐，而后从右往左进行计算。

要想让两个链表右端对齐，咱们有两种实现形式。

将两个链表进行反转，而后间接求和。
借助栈这种先进后出的个性，来实现链表的右端对齐。

咱们先来看一下如何应用链表反转来实现。

class Solution(object):    def reverse(self, head):        cur = head        #初始化时，pre为None        pre = None        while cur:            next=cur.next            cur.next = pre            pre = cur            cur = next        return pre    def addTwoNumbers(self, l1, l2):        #将两个链表翻转        l1 = self.reverse(l1)        l2 = self.reverse(l2)        head=ListNode(0)        pre=head        #代表是否进位        carray=0        while l1 or l2:           v1=l1.val if l1 else 0           v2=l2.val if l2 else 0           sum=v1+v2+carray           #进位数           carray=int(sum/10)           tmp=sum%10           node=ListNode(tmp)           pre.next=node           pre=pre.next           if l1:               l1=l1.next           if l2:               l2=l2.next        if carray==1:            node=ListNode(carray)            pre.next=node                return self.reverse(head.next)

上面咱们来看一下如何应用栈来求解。咱们首先将两个链表从头到尾放入两个栈中，而后每次同时出栈，就能够实现链表的右端对齐相加，咱们来看一下代码如何实现。

def addTwoNumbers(l1, l2):    #申请两个栈    stack1=[]    stack2=[]    #l1入栈    while l1:        stack1.append(l1.val)        l1 = l1.next    while l2:        stack2.append(l2.val)        l2 = l2.next    head = None    carry = 0    while stack1 and stack2:        num = stack1.pop() + stack2.pop() + carry        #求进位数        carry=int(num/10)        tmp=num%10        node = ListNode(tmp)        node.next = head        head = node    s = stack1 if stack1 else stack2    while s:        num = s.pop() + carry        carry = int(num / 10)        tmp = num % 10        node = ListNode(tmp)        node.next = head        head = node    if carry==1:        node = ListNode(carry)        node.next = head        head = node    return head

单链表的排序

问题形容

LeetCode 148. 排序链表

给定一个节点数为n的无序单链表，对其按升序排序。

要求：空间复杂度 O(n)，工夫复杂度 O(nlogn)。

示例：

输出：[-1,0,-2]

返回值：{-2,-1,0}

剖析问题

因为题目要求工夫复杂度是O(nlogn)，那工夫复杂度是O(nlogn)的排序算法有归并排序、疾速排序和堆排序，其中最适宜链表的排序算法是归并排序。

归并排序是基于分治思维，最容易想到的就是自顶向下的递归实现。自顶向下的递归实现次要包含二个环节。

宰割环节
- 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点能够应用快慢指针法，快指针每次挪动2步，慢指针每次挪动1步，当快指针走到链表的开端时，慢指针恰好指向了链表的中点地位。
- 找到中点后，将链表在中点处宰割成两个子链表。
- 而后递归的进行宰割，直到宰割后的链表只有一个节点或者为Null。这时，宰割的子链表都是有序的，因为只蕴含一个节点。
合并环节
- 将两个有序的链表合并成一个有序链表。咱们能够采纳双指针法求解。
- 递归执行，直到合并实现。

class Solution:    def sortList(self, head):        #如果链表为空或者只蕴含一个节点，递归终止        if not head or not head.next:            return head        #应用快慢指针法来寻找链表的中点        slow=head        fast=head.next        while fast and fast.next:            fast=fast.next.next            slow=slow.next        #slow指向的就是链表的中点，将链表在中点处进行宰割        head2=slow.next        slow.next=None        #递归的切割宰割链表        left = self.sortList(head)        right = self.sortList(head2)        #合并链表，应用双指针法        tmp = res = ListNode(0)        while left and right:            if left.val < right.val:                tmp.next=left                left=left.next            else:                tmp.next=right                right=right.next            tmp=tmp.next        if left:            tmp.next=left        else:            tmp.next=right        return res.next

该算法的工夫复杂度是O(n)。因为自顶向下是通过递归来实现的，如果思考递归调用栈的栈空间，那么该算法的空间复杂度是O(logn)。

优化

咱们也能够采纳自底向上的办法来求解。

首先，咱们求出链表的长度length。而后将链表拆分成子链表进行合并。

咱们用sublength示意每次须要排序的子链表的长度，初始时sublength=1。
每次将链表拆分成若干个长度为sublength的子链表（最初一个子链表的长度可能小于sublength），依照每两个子链表一组进行合并，合并后即能够失去若干个长度为sublength 2的有序子链表（最初一个子链表的长度可能小于sublength 2）。
将sublength的值加倍，反复第二步，而后对更长的有序子链表进行合并，直到有序子链表的长度大于或等于链表的长度，这样整个链表的排序就实现了。

咱们来看一下代码的实现。

class Solution:    def sortList(self, head):        #合并两个有序链表        def merge(head1, head2):            #哨兵节点            dummyHead = ListNode(0)            temp=dummyHead            while head1 and head2:                if head1.val <= head2.val:                    temp.next = head1                    head1 = head1.next                else:                    temp.next = head2                    head2 = head2.next                temp = temp.next            if head1:                temp.next = head1            else:                temp.next = head2            return dummyHead.next        #如果链表为空，间接返回        if not head:            return head        #遍历一遍链表，求出链表的长度        length = 0        node = head        while node:            length += 1            node = node.next        #创立一个哨兵节点,指向链表头        dummyHead = ListNode(0)        dummyHead.next=head        #初始时，子链表的长度为1        subLength = 1        while subLength < length:            prev=dummyHead            cur=dummyHead.next            while cur:                #截取长度为subLength的子链表head1                head1 = cur                for i in range(1, subLength):                    if cur.next:                        cur = cur.next                    else:                        break                head2 = cur.next                cur.next = None                #截取长度为subLength的子链表head2                cur = head2                for i in range(1, subLength):                    if cur and cur.next:                        cur = cur.next                    else:                        break                #截取完后残余的链表节点                surplus_head = None                if cur:                    surplus_head = cur.next                    cur.next = None                #将两个有序链表进行合并                merged = merge(head1, head2)                #将排好序的链表插入到新生成的链表里                prev.next = merged                #将指针挪动到链表的开端                while prev.next:                    prev = prev.next                #持续合并残余的节点                cur=surplus_head            subLength = subLength * 2        return dummyHead.next

该算法的工夫复杂度是O(nlogn)，空间复杂度是O(1)。

判断一个链表是否为回文结构

问题形容

LeetCode 剑指 Offer II 027. 回文链表

给定一个链表，请判断该链表是否为回文结构。回文是指该字符串正序逆序完全一致。

示例：

输出：{1,2,2,1}

输入：true

阐明：1 -> 2 -> 2 -> 1

剖析问题

回文串是斧正读反读都一样的字符串，最简略的是应用双指针法。然而对于链表这种数据结构来说，指针只能向一个方向挪动，也就是说只能找到后继节点，没方法找到前驱节点。所以没方法应用双指针法，要想应用双指针，咱们就须要把链表元素放入一个数组中，而后再去判断是否是回文，这须要O（n）的空间复杂度，这里就不在赘述。大家能够去看第44题。

咱们能够这么思考，将链表的后半局部进行反转，而后将前半部分和后半局部进行比拟，如果雷同就代表是回文链表，否则不是回文链表。寻找链表的中点咱们能够应用快慢指针的形式。

快慢指针寻找链表中点。

对链表的后半局部进行翻转

前半部分和后半局部进行比拟。

class Solution:    def isPalindrome(self, head) -> bool:        #链表为空，间接返回true        if head is None:            return True        #找到链表的中点        middle_point = self.middle_point(head)        second_start = self.reverse_list(middle_point.next)        #判断前半部分和后半局部是否相等        result = True        first = head        second = second_start        while result and second is not None:            if first.val != second.val:                result = False            first = first.next            second = second.next        #还原链表并返回后果        middle_point.next = self.reverse_list(second_start)        return result    #快慢指针寻找中点    def middle_point(self, head):        fast = head        slow = head        while fast.next is not None and fast.next.next is not None:            fast = fast.next.next            slow = slow.next        return slow    #翻转链表    def reverse_list(self, head):        previous = None        current = head        while current is not None:            next_node = current.next            current.next = previous            previous = current            current = next_node        return previous

链表内指定区间反转

问题形容

LeetCode 92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从地位 left 到地位 right 的链表节点，返回反转后的链表。

示例：

输出：head = [1,2,3,4,5]， left = 2，right = 4

输入：[1,4,3,2,5]

剖析问题

对于链表相干的题目，咱们肯定要先想分明思路，搞懂指针挪动的先后顺序。

对于这道题，咱们能够采纳头插法来求解。在链表反转的区间内，当咱们每次遍历到一个节点时，就让该节点插入到反转局部的起始地位。如下图所示：

具体来说，咱们定义三个指针pre、cur、next变量。

咱们首先将pre挪动到第一个要反转的节点的后面，即pre->next=left
而后将指针cur挪动到第一个要反转的节点地位上，即cur=left，
而后将 cur->next 赋值给变量next。
将cur的下一个节点指向next的下一个节点，即cur->next=next->next
而后将next的下一个节点指向pre的下一个节点，即next->next=pre->next
而后将next插入到链表头部，即pre->next=next。
而后周而复始执行3、4、5、6，直到反转完链表区间内的节点。

上面咱们来看一下代码如何实现。

class Solution:    def reverseBetween(self, head, left, right):        #设置哨兵节点，对于链表相干的问题，咱们通过设置哨兵节点        #能够省去边界条件的判断        dummynode = ListNode(-1)        #哨兵节点指向链表头        dummynode.next = head        pre = dummynode        #遍历，使得pre指向链表反转局部        #的第一个结点left        for _ in range(left - 1):            pre = pre.next        #cur指向链表反转局部的第一个节点        cur = pre.next        for _ in range(right - left):            next = cur.next            cur.next = next.next            next.next = pre.next            pre.next = next        return dummynode.next

该算法的工夫复杂度是O(N)，其中 N 是链表总节点数。最多只遍历了链表一次，就实现了反转。空间复杂度是O(1)，只用到了常数个变量。

删除有序链表中反复的元素-I

问题形容

LeetCode 83. 删除排序链表中的反复元素

删除给出链表中的反复元素（链表中元素从小到大有序），使链表中的所有元素都只呈现一次。

示例：

输出：{1,1,2}

输入：{1,2}

剖析问题

因为给定的链表是排好序的，所以咱们能够晓得反复的元素在链表中呈现的地位肯定是间断的，因而咱们只须要对链表进行一次遍历，就能够删除反复的元素。

开始时，咱们定义一个指针cur指向链表的头结点，而后开始对链表进行遍历。如果cur.val==cur.next.val时，咱们就将cur.next这个节点从链表中移除；如果不雷同，咱们将指针cur后移，即cur=cur.next。当遍历残缺个链表之后，咱们返回链表的头结点即可。

上面咱们来看一下代码的实现。

class Solution:    def deleteDuplicates(self, head):        #如果链表为空，间接返回        if not head:            return head        #cur指向头结点        cur = head        #当cur.next不为空时        while cur.next:            #如果值雷同，删除cur.next节点            if cur.val == cur.next.val:                cur.next = cur.next.next            #否则cur后移            else:                cur = cur.next        return head

该算法的工夫复杂度是O(N)，空间复杂度是O(1)。

删除有序链表中反复的元素-II

问题形容

LeetCode 82. 删除排序链表中的反复元素 II

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字反复状况的节点，只保留原始链表中没有反复呈现的数字。返回同样按升序排列的后果链表。

示例:

输出：head = [1，2，3，3，4，5]

输入：[1，2，5]

剖析问题

因为给定的链表是有序的，所以链表中反复的元素在地位上必定是相邻的。因而，咱们能够对链表进行一次遍历，就能够删除反复的元素。

这里须要留神一点，因为可能会删除头结点head，咱们引入了一个哨兵节点dummy，让dummy.next=head，这样即便head被删除了，那么也会操作dummy.next指向新的链表头结点，所以最终返回dummy.next即可。

首先，咱们让cur指针指向链表的哨兵节点，而后开始对链表进行遍历。如果cur.next与cur.next.next对应的元素值雷同，那么咱们就须要将cur.next以及前面所有值雷同的链表节点全副删除，直到cur.next为空节点或者其元素值与其不同。如果cur.next与cur.next.next对应的元素值不雷同，那么咱们就能够将cur 指向 cur.next。

上面咱们来看一下代码的实现。

class Solution:    def deleteDuplicates(self, head):        #如果链表为空，间接返回        if not head:            return head        #创立一个哨兵节点        dummy = ListNode(0)        dummy.next=head        #开始时，将cur指向哨兵节点        cur = dummy        while cur.next and cur.next.next:            #如果cur.next.val和cur.next.next.val雷同，删除反复元素            if cur.next.val == cur.next.next.val:                data = cur.next.val                while cur.next and cur.next.val == data:                    cur.next = cur.next.next            else:                cur = cur.next        return dummy.next

该算法的工夫复杂度是O(n)，空间复杂度是O(1)。

链表的奇偶重排

问题形容

LeetCode 328. 奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点别离排在一起。请留神，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

示例：

输出：{1，2，3，4，5，6}

输入：{1，3，5，2，4，6}

剖析问题

要想把一个链表的奇数节点和偶数节点别离排在一起，咱们能够先拆散链表，把一个链表拆分成两个链表，其中一个是奇数链表，另一个是偶数链表，最初将偶数链表拼接在奇数链表后即可。

咱们都晓得，对于一个链表来说，相邻节点的奇偶性是不同的。原始链表的头节点head是奇数链表的头节点，head的后一个节点是偶数链表的头节点，咱们假如是evenHead ，则evenHead = head.next。咱们保护两个指针odd和even别离指向奇数链表和偶数链表的最初一个节点，初始时 odd=head，even=evenHead。通过一直的更新odd和even，将链表宰割成奇数链表和偶数链表。

更新奇数节点，咱们令 odd.next=even.next，此时奇数链表的最初一个节点指向了偶数节点even的后一个节点。而后令odd=odd.next，此时odd变成了even的后一个节点。
更新偶数节点，咱们令 even.next=odd.next，此时偶数节点的最初一个节点指向了奇数节点odd的后一个节点。而后令even=even.next，此时even变成了odd的后一个节点。

通过以上两步，咱们就实现了对一个奇数节点和一个偶数节点的拆散。反复上述操作，直到全副节点拆散实现。最初令 odd.next = evenHead，将偶数链表连贯在奇数链表之后，即实现了奇数链表和偶数链表的合并。

上面咱们来看一下代码的实现。

class Solution:    def oddEvenList(self, head):        #如果链表为空，间接返回        if not head:            return head        #evenHead指向偶数链表的头节点        evenHead = head.next        #指向奇数链表和偶数链表的开端节点        odd = head        even = evenHead        while even and even.next:            #奇数链表的开端节点指向偶数节点的下一个节点            odd.next = even.next            #奇数链表开端节点后移            odd = odd.next            #偶数链表的开端节点指向奇数节点的下一个节点            even.next = odd.next            #偶数链表开端节点后移            even = even.next        #偶数链表连贯到奇数链表的开端        odd.next = evenHead        return head

该算法的工夫复杂度是O(n)，空间复杂度是O(1)。

重排链表

问题形容

LeetCode 143. 重排链表

给定一个单链表 L 的头节点head ，单链表 L 示意为：L₀ -> L₁ -> ... -> L_n-1 -> L_n，将其重新排列后变成 L₀ -> L_n -> L₁ -> L_n-1 -> ...。不能只是单纯的扭转节点的值，而须要理论的进行节点的替换。

示例：

输出： head = [1，2，3，4]

输入： [1，4，2，3]

剖析问题

首先，咱们来察看一下链表重置前和重置后的变动。如下图所示：

咱们能够晓得，重置后的链表是将原链表的左半端和反转后的右半段进行节点穿插合并而成的，所有咱们能够分三步来求解。

找到原链表的中点，将链表宰割成左右两局部。
对后半局部进行反转。
建原链表的左半局部和反转后的右半局部进行合并。

class Solution:    def reorderList(self, head):        #如果链表为空，间接返回        if not head:            return        #寻找链表的中点，将链表宰割成左右两局部        mid = self.middleNode(head)        left = head        right = mid.next        mid.next = None        #对右半局部的链表进行反转        right = self.reverseList(right)        #左右链表进行合并        self.mergeList(left, right)    def middleNode(self, head):        #应用快慢指针法求中点        slow = fast = head        while fast.next and fast.next.next:            slow = slow.next            fast = fast.next.next        return slow    #对链表进行反转    def reverseList(self, head):        prev = None        curr = head        while curr:            tmp = curr.next            curr.next = prev            prev = curr            curr = tmp        return prev    #对两个链表进行合并操作    def mergeList(self, l1, l2):        #l1和l2的节点数量相差不会超过一个        #所以间接合并就好        while l1 and l2:            tmp1 = l1.next            tmp2 = l2.next            l1.next = l2            l1 = tmp1            l2.next = l1            l2 = tmp2

该算法的工夫复杂度是O(N)，空间复杂度是O(1)。

链表中倒数最初k个节点

问题形容

LeetCode 剑指 Offer 22. 链表中倒数第k个节点

输出一个链表，输入该链表中倒数第k个节点。为了合乎大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值顺次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

输出：{1,2,3,4,5}，2

输入：{4,5}

剖析问题

这道题比较简单，咱们能够间接应用快慢指针来求解，开始时申请两个指针同时指向链表的头结点，记为slow和fast，而后让fast先挪动k步，再而后让两个指针slow和fast同时挪动，使得fast和slow在挪动的过程中总是相隔k个单位，当fast指针走到开端的时候，此时slow正好指向的是倒数第k个地位。

上面咱们来看一下代码的实现。

class Solution:    def FindKthToTail(self, pHead, k):        #快慢指针同时执行头结点        slow=fast=pHead        #快指针挪动k步        for i in range(0,k):            #如果还没走完k步就走到了链表尾，间接返回None            if not fast:                ‘return None            fast = fast.next        #两个指针同时挪动,直到fast为空        while fast:            slow=slow.next            fast=fast.next        return slow

划分链表

问题形容

LeetCode 面试题 02.04. 宰割链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都呈现在大于或等于 x 的节点之前。并且两个局部之内的节点之间与原来的链表要放弃绝对程序不变。

示例：

输出：head = [1,4,3,2,5,2], x = 3

输入：[1,2,2,4,3,5]

剖析问题

简略来说，咱们只须要保护两个链表small和large即可，使得small链表按顺序存储所有小于x的节点，large链表按顺序存储所有大于等于x的节点。当咱们遍历完链表之后，只须要将small链表的尾节点指向large链表的头结点即可实现宰割链表的操作。

首先，咱们创立两个节点smallHead和largeHead别离为两个链表的哑结点，这是为了不便的解决头结点为空的边界条件，同时smallTail和largeTail别离指向两个链表的开端节点。开始时，smallHead=smallTail，largeHead=largeTail，而后从前往后遍历链表head，判断以后节点的值是否小于x，如果小于x，就将smallTail的next指针指向该节点，否则将largeTail的next指针指向该节点。

遍历完结后，咱们将largeTail的next指针置为空，这是因为以后节点复用的是原链表的节点，而其 next 指针可能指向一个小于 x的节点，咱们须要切断这个援用。而后将smallTail的next指针指向largeHead的next指针指向的节点，来将两个链表合并起来，最初返回smallHead.next即可。

上面咱们来看一下代码实现。

class Solution(object):    def partition(self, head, x):        #创立两个哑结点        smallHead = smallTail = ListNode(0)        largeHead = largeTail = ListNode(0)        #遍历链表        while head:            #如果head.val<x,将以后节点插入small中，否则插入large中            if head.val < x:                smallTail.next=head                smallTail=smallTail.next            else:                largeTail.next=head                largeTail=largeTail.next            head=head.next        largeTail.next=None        #合并两个链表        smallTail.next=largeHead.next        return smallHead.next

该算法的工夫复杂度是O(n)，空间复杂度是O(1)。