算法刷题笔记02：Linked List

Hsinyan

发布于 2022-08-30 15:22:16

1620

发布于 2022-08-30 15:22:16

文章被收录于专栏：Hsinyan写字的地方Hsinyan写字的地方

Linked List

206.反转链表

题目描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

题目链接：https://leetcode-cn.com/problems/reverse-linked-list/

解法一：迭代

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pre = None
        cur = head

        # 跳出循环条件
        while cur:
            # 暂存下个结点
            temp_next = cur.next
            # 将当前结点指向前一个值
            cur.next = pre
            # pre和cur都进一步
            pre = cur
            cur = temp_next
        
        return pre

解法二：递归

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or head.next == None:
            return head
        
        res = self.reverseList(head.next)
        # 将下个结点指向自己
        head.next.next = head
        # 避免链表循环
        head.next = None

        return res

24.两两交换链表中的节点

题目描述

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

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

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

题目链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs

解法一：借用栈

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # Linked List题目特殊情况处理
        if not head or head.next == None:
            return head

        # dummy结点
        p = ListNode(-1)

        # 记录当前结点
        cur = head
        # 记录头结点.等到程序结束返回head.next即可
        head = p
        # 用stack保存每次迭代的两个节点
        stack = []

        while cur and cur.next:
            # 栈入
            stack.append(cur)
            stack.append(cur.next)
            # 当前结点移动2个位置
            cur = cur.next.next
            # 栈出操作，指向
            p.next = stack.pop()
            p.next.next = stack.pop()
            # 移动p
            p = p.next.next
        
        # 边界条件判断，奇数时候会出现第一种情况，直接指向cur即可
        if cur:
            p.next = cur
        else:
            p.next = None
        
        return head.next

解法二：迭代

class Solution(object):
    def swapPairs(self, head):
        # 增加一个特殊节点方便处理
        p = ListNode(-1)
        # 创建a，b两个指针，这里还需要一个tmp指针
        a,b,p.next,tmp = p,p,head,p
        while b.next and b.next.next:
        # a前进一位，b前进两位
            a,b = a.next,b.next.next
            # 这步很关键，tmp指针用来处理边界条件的
            # 假设链表是1->2->3->4，a指向1，b指向2
            # 改变a和b的指向，于是就变成2->1，但是1指向谁呢？
            # 1是不能指向2的next，1应该指向4，而循环迭代的时候一次处理2个节点
            # 1和2的关系弄清楚了，3和4的关系也能弄清楚，但需要一个指针来处理
            # 2->1，4->3的关系，tmp指针就是干这个用的
            tmp.next,a.next,b.next = b,b.next,a
            # 现在链表就变成2->1->3->4
            # tmp和b都指向1节点，等下次迭代的时候
            # a就变成3，b就变成4，然后tmp就指向b，也就是1指向4
            tmp,b = a,a
        return p.next

这里的迭代做法从 LeetCode 题解抄过来，感觉有点绕，涉及到了三个指针，不是很能理解。

参考链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/dong-hua-yan-shi-24-liang-liang-jiao-huan-lian-bia/

解法三：递归

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        # 边界条件判断
        if not head or head.next == None:
            return head
        # 从第3个链表往后进行交换
        third = self.swapPairs(head.next.next)
        # 从第3个链表往后都交换完了，我们只需要交换前两个链表即可,
        # 这里我们把链表分为3组，分别是第1个节点，第2个节点，后面
        # 的所有节点，也就是1→2→3，我们要把它变为2→1→3
        second = head.next
        head.next = third
        second.next = head

        return second