七十一、去重交换排序链表、 求链表的中间结点

「@Author：Runsen」

❝

编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题进行代码化。「---- Runsen」

❞

最近在重新梳理学算法的知识，本文为链表常见操作复习的总结文章，会讲解常见的链表题目实现思路及附上答案，这些题目在leetcode上对应的题号也有给出，好好学习算法吧～

• 两两交换链表的节点
• 删除排序链表中的重复元素
• 排序链表（重要）
• 链表的中间结点

leetcode 对应题号：24，83，148，876

LeetCode  第24题：两两交换链表的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

示例: 
给定 1->2->3->4, 你应该返回 2->1->4->3.

1——2——3——4：我们需要做的就是，将一指向三，将二指向一，如此我们就完成了反转，后续只要一次遍历即可。

思路：a,b,pre记录三个指针，相邻两个，相邻两个元素前面的一个，第一步将节点 2 指向节点 1，然后再将节点 1 指向节点三。这一步交换完毕后链表变为 2->1->3->4。在进行下一次交换，将节点 4 指向节点 3，节点3指向none 但是还要注意节点 1 的指向，节点 1 要指向节点 4。

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

class Solution:
 def swapPairs(self,head):
     pre, pre.next = self, head
     while pre.next and pre.next.next:
         a = pre.next
         b = a.next
         pre.next,b.next ,a.next = b,a,b.next
         pre = a
         
     return  self.next

eetCode  第83题：删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1: 
输入: 1->1->2
输出: 1->2
示例 2: 
输入: 1->1->2->3->3
输出: 1->2->3 

由于输入的列表已排序，因此我们可以通过将结点的值与它之后的结点进行比较来确定它是否为重复结点。如果它是重复的，我们更改当前结点的 next 指针，以便它跳过下一个结点并直接指向下一个结点之后的结点。

如果遇到cur.val和cur.next.val重复,让cur.next=cur.next.next

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

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        h = head
        while head and head.next:
            if head.val == head.next.val:
                head.next = head.next.next
            else:
                head = head.next
                
        return h

class Solution:
    def deleteDuplicates(self, head):
        cur = root = head
        while head:
            if head.val != cur.val:
                cur.next = cur = head
            head = cur.next = head.next
        return root

LeetCode 第 876题：链表的中间结点（重要）

# 输入：[1,2,3,4,5]
#输出：此列表中的结点 3 (序列化形式：[3,4,5])
#返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
#注意，我们返回了一个 ListNode 类型的对象 ans，这样：
#ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
# 示例 2： 
# 输入：[1,2,3,4,5,6]
#输出：此列表中的结点 4 (序列化形式：[4,5,6])
#由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
# 提示： 
# 给定链表的结点数介于 1 和 100 之间。 
# Related Topics 链表

「寻找链表的中间结点」

• 遍历两次。第一次遍历求导链表长度，找出中间结点的长度值，第二层遍历找到中间结点并返回；
• 快慢指针法。慢指针每次走一步，快指针每次走两步，快指针走到链表末尾时，慢指针刚好走到链表中间。

「方法２时间复杂度更低，只需遍历一次。」

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

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = head
        fast = head
        while  fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

eetCode 第148题：排序链表（重要）

在 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2: 
输入: -1->5->3->4->0
输出: -1->0->3->4->5 

题目要求时间空间复杂度分别为和，根据时间复杂度我们自然想到二分法，从而联想到归并排序。归并排序，后面细聊。

利用归并的思想，递归地将当前链表分为两段，然后merge，分两段的方法是使用 fast-slow 法，用两个指针，一个每次走两步，一个走一步，直到快的走到了末尾，然后慢的所在位置就是中间位置，这样就分成了两段。

归并排序分为两步，

1.找到待排序链表的中间节点（使用快慢指针法，leetcode 876题）

2.合并两个有序链表（leetcode 21题），因此本题相当于结合这两步来实现链表排序。

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        # if not head or not head.next:#
        if head == None or head.next == None:
            return head 
        slow  = head #快慢指针法找到链表中点
        fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        right = slow.next
        # print(right.val)
        slow.next = None #这一句的原因是 需要对中点前的链表进行割断处理

        l1 = self.sortList(head)#递归保证l1和l2为有序链表
        l2 = self.sortList(right)
        return self.mergeTwoLists(l1,l2)
   # 合并两个有序链表
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1 and not l2:
            return None
        if not l1:
            return l2
        if not l2:
            return l1
        head = head1 = ListNode(0)
        while l1 and l2:
            if l1.val <= l2.val:
                head.next = l1
                l1 = l1.next
            else:
                head.next = l2
                l2 = l2.next
            head = head.next
        if not l1 : head.next = l2
        if not l2 : head.next = l1
        return head1.next

下面是测试代码

if __name__ == "__main__":
    n1 = ListNode(4)
    n2 = ListNode(7)
    n3 = ListNode(6)
    n4 = ListNode(9)
    n5 = ListNode(12)
    m=n1
    n1.next=n2
    n2.next=n3
    n3.next=n4
    n4.next=n5
    print('原链表的节点：')    
    while m:
        print('节点%d的值:'%(m.val),m.val)
        m=m.next
    print('\n排序之后的节点：')

    s=Solution()
    s.sortList(n1)
    while n1:
        print('节点%d的值:'%(n1.val),n1.val)
        n1=n1.next
#result
原链表的节点：
节点4的值: 4
节点7的值: 7
节点6的值: 6
节点9的值: 9
节点12的值: 12

排序之后的节点：
节点4的值: 4
节点6的值: 6
节点7的值: 7
节点9的值: 9
节点12的值: 12

这个链表排序基于归并排序算法。首先，遍历整个链表，确定链表中元素个数，同时也可以确定链表的中间位置；然后从中间位置切断链表(mid->key=NULL）；然后递归地给两个链表进行排序；最后，合并两个有序链表，形成一个完整的有序链表。整个算法的时间复杂度为O(n long)，空间复杂度为O(1)。

「人生最重要的不是所站的位置，而是内心所朝的方向。只要我在每篇博文中写得自己体会，修炼身心；在每天的不断重复学习中，耐住寂寞，练就真功，不畏艰难，奋勇前行，不忘初心，砥砺前行，人生定会有所收获，不留遗憾 （作者：Runsen ）」

❝

本文已收录 GitHub，传送门~^[1] ，里面更有大厂面试完整考点，欢迎 Star。

❞

Reference