剑指offer：反转链表（Java）

stonezhu 发布于2019-08-16 18:39 / 1946人阅读

摘要：问题描述输入一个链表，反转链表后，输出新链表的表头。通过循环遍历当前链表，在遍历过程中反转链表，当前节点遍历到最后为时，循环停止，此时当前节点为，所以它的前一个节点就是新链表的第一个节点。

1.问题描述

输入一个链表，反转链表后，输出新链表的表头。

2.思路

首先要判断给出的头节点是否为空，如果为空直接返回，如果不为空才可以进行反转。
因为每个节点只有一个next指针记录它的下一个节点的地址，所以应该需要两个变量分别记录当前节点左右两边的节点，否则反转链表之后就没办法连上后面的节点了。
通过循环遍历当前链表，在遍历过程中反转链表，当前节点遍历到最后为null时，循环停止，此时当前节点为null，所以它的前一个节点就是新链表的第一个节点。
注意：当前节点的前一个节点是从null开始的，当前节点一定要放在中间，记录它的前后各一个节点，否则循环过程易错。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null)
            return head;    //head为null直接返回。
        ListNode pNode = head;    //表示当前节点
        ListNode pre = null;    //当前节点的前一个节点
        ListNode next = null;    //当前节点的后一个节点
        while(pNode != null){
            next = pNode.next;    //记录下当前节点的下一个节点
            pNode.next = pre; //反转链表
            pre = pNode;    //让prej和pNode都向后移动一位，next不用变了，因为上面会自动根据pNode获取next节点。
            pNode = next;
        }
        return pre;
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/75507.html

剑指offer系列——剑指 Offer 24. 反转链表（C语言）

摘要：假设反转对象节点为，反转指向的结点为，反转后指向的结点为首结点。当然也可以根据栈先进后出的特点，使用栈反转链表。 ⭐️前面的话⭐️ 大家好！博主开辟了一个新的专栏—...

weakish 2021-09-03 10:29 评论0 收藏0
剑指offer系列——剑指 Offer 06. 从尾到头打印链表（C语言）

摘要：导航小助手剑指从尾到头打印链表题目详情解题思路源代码总结剑指从尾到头打印链表题目详情输入一个链表的头节点，从尾到头反过来返回每个节点的值用数组返回。时间复杂度方法先反转链表并求长度，在将反转后的链表数据拷贝至数组中。 ...

DevTTL 2021-09-04 16:41 评论0 收藏0
LeetCode 精选TOP面试题【51 ~ 100】

摘要：有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像，都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归，所以空间复杂度为 ...

Clect 2021-11-15 11:38 评论0 收藏0
剑指offer:合并两个排序的链表（Java）

摘要：问题描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 1.问题描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 2.思路方法1:非递归方法根据题目这个很类似排序中的外排过程,两个数组分别排好序,然后再把他们整体进行排序.所以这道题思想很简单,就是用两个变量分别遍历两个链表.比较遍历到...

darkbaby123 2019-08-16 18:39 评论0 收藏0