首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

如何仅使用两个指针反转单链表?

要反转单链表,只需要使用两个指针。一个指针用于遍历链表,另一个指针用于记录当前节点的前一个节点。在遍历过程中,将当前节点的下一个节点指向前一个节点,然后将前一个节点和当前节点向前移动一个节点。当遍历到链表末尾时,链表就被反转了。

以下是使用Python实现的代码示例:

代码语言:python
代码运行次数:0
复制
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head: ListNode) -> ListNode:
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

在这个示例中,ListNode类表示链表中的一个节点,包含一个值和一个指向下一个节点的指针。reverse_list函数接受一个链表的头节点,并返回反转后的链表的头节点。

在函数中,prev指针指向当前节点的前一个节点,curr指针用于遍历链表。在遍历过程中,将当前节点的下一个节点指向前一个节点,然后将prevcurr向前移动一个节点。当遍历到链表末尾时,链表就被反转了。

这种方法只需要使用两个指针,因此具有较高的效率。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

  • 快慢指针巧解链表题目(二)

    输入:[1,2,3,4,5] 输出:此列表中的节点 3思路分析:要找到链表的中间节点,可以定义两个指针,一个是慢指针slow,另一个是快指针fast。初始,慢指针slow和快指针fast都指向链表的头节点。然后,快指针fast每次向前移动两步,慢指针slow每次向前移动一步,当快指针fast不能继续向前移动时,慢指针slow所指的节点就是中间节点。对于节点个数为奇数的链表来说,其中间节点只有一个;而对于节点个数为偶数的链表来说,其中间节点有两个。接着,我们就通过动画来看下如何通过快慢指针找到链表的中间节点。1.当快指针fast向前移动的条件是:fast.next!=null && fast.next.next != null时:对于节点个数为奇数的链表来说,动画演示如下,此时链表的中间节点是节点3。对于节点个数为偶数的链表来说,动画演示如下,此时链表的中间节点是节点2,即在2和3这两个中间节点中,找到是第一个中间节点。2.当快指针fast向前移动的条件是:fast!=null && fast.next != null时:对于节点个数为奇数的链表来说,动画演示如下,此时链表的中间节点是节点3。对于节点个数为偶数的链表来说,动画演示如下,此时链表的中间节点是节点3,即在2和3这两个中间节点中,找到是第二个中间节点。 题目要求的是如果有两个中间节点,则返回第二个中间节点。因此,对于该题目而言,快指针fast向前移动的条件是:fast!=null && fast.next != null。代码实现: 02LeetCode #206反转链表题目描述:反转一个单链表。示例:输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL思路分析:对于题目给出的链表,简化如下:由于只知道链表的头节点head,因此需要从头节点head开始反转。头节点head在反转之后,就成为了链表的尾节点,而尾节点的后继指针是指向null的。因此,需要定义一个空节点,在这里我们用prev表示。同时,对于当前考察的节点,我们用cur表示。接着要做的就是,将cur所指节点的后继指针指向prev指向的节点。但是,这么做之后,cur所指节点的原本的后继节点就从链表中丢失了。因此,在将cur所指节点的后继指针指向prev指向的节点前,需要先用变量nextNode指向cur所指节点的原本的后继节点。 在完成cur所指节点的反转之后,就要继续反转下一个节点了。因此,先prev指向cur所指向的节点,作为下一个待反转节点反转之后的后继节点。然后,cur指向nextNode指向的节点,表示其是下一个待反转的节点。动画演示:代码实现: 03LeetCode #143重排链表题目描述:给定一个单链表 L:L0→L1→…→Ln-1→Ln , 将其重新排列后变为:L0→Ln→L1→Ln-1→L2→Ln-2→…你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。示例1:给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.示例2:给定链表 1->2->3->4, 重新排列为 1->4->2->3.思路分析:通过观察给到的示例,其结果是将原链表的前半部分和原链表的后半部分反转之后的链表进行合并得到的。因此,整体思路就是:首先,找到链表的中间节点,方法如上述的#86题;接着,将链表的后半部分反转,放入如上述的#206题;然后,将链表的前半部分和链表的后半部分反转后的结果进行合并。 示例1给出的链表结构如下:中间节点是节点3,链表的前半部分和后半部分如下:链表合并的动画演示如下:整个题目的完整代码实现如下:

    02
    领券