算法题:反转一个单链表&判断链表是否有环

仅分享个人比较喜欢的解法,有兴趣可以自己继续探究。题目来源于力扣

理论基础

数组&链表

反转单链表

题目描述

反转一个单链表

示例:

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

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

解题思路

双指针迭代

Python 解法

def reverseList(self, head):
    cur = head
    prev = None

    while cur:
        # 记录当前节点的下一个节点
        tmp = cur.next
        # 然后将当前节点指向prev
        cur.next = prev
        # pre和cur节点都前进一位
        prev = cur
        cur = tmp
    return pre

# 简洁写法
def reverseList(self, head):
    cur, prev = head, None
    while cur:
        cur.next, prev, cur = prev, cur, cur.next
    return prev

链表交换相邻元素

题目描述

链表交换相邻元素

解题思路

存在a、b(a.next)

把a, b 交换成 b,a

更新pre指针

Python 解法

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

判断链表中是否有环

题目描述

给定一个链表,判断链表中是否有环

解题思路

  1. 判重,判断每一个元素是否已经访问过了

  2. 快慢指针,判断两个指针是否能相遇

Python 解法

#快慢指针
def hasCycle(self, head):
    fast = slow = head
    while slow and fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!