力扣 206.翻转链表

力扣 206.翻转链表

文章目录

• 题目链接
• 源代码 github 地址
• 1、题目要求
• 2、思路分析（双指针发解决）
• 3、执行代码 - Java
• 4、问题反思
• 5、小结

题目链接

https://leetcode-cn.com/problems/reverse-linked-list/

源代码 github 地址

https://github.com/YIMEng-0/DataStructure

1、题目要求

题意：反转一个单链表。

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

2、思路分析（双指针发解决）

定义两个指针：
pre 刚开始指向 null ；
cur 指向头结点，也就是链表的第一个结点；
依次遍历，将指针的方向改变；
注：需要定义 temp 结点，作为保存 cur.next 不然 cur.next 指向了 pre 之后，后面的链表数据就消失了；

3、执行代码 - Java

public class ReverselinkedList {
    public ListNode reverselinkedList(ListNode head) {
        // 将链表的头结点传递进来进行链表的翻转 *** 作
        ListNode temp; // 保存cur.next 防止找不到链表的其余部分；
        ListNode cur = head;
        ListNode pre = null;

        while (cur != null) {
            temp = cur.next;
            cur.next = pre; // 指针调整方向

            pre = cur;
            cur = temp;
        }

        return pre; // 不是返回 cur 因为 cur 最终指向了空，一个链表不能最终的头结点是一个空
    }
}

4、问题反思

1、为什么定义 temp 结点？
因为要保存后面的链表信息， cur.next 会先指向前面的结点，没有 temp 没有事先保存 cur.next 结点信息的话，后面的链表是会丢失的；

2、在数据结构中的 = 和普通情况下的 = 都是赋值，这里赋值的是地址，在理解的时候可以理解为指针的移动，左边的指针向着右边进行移动，表现为：左边指针 = 右边指针；

3、为什么这里翻转链表返回的是 pre 指针？
因为返回的是链表的头结点，这个时候的 cur 指向到了空的位置，pre 指向的是链表的最后一个位置，所以，返回的是 pre

4、为什么是 pre = cur; cur = temp; ? 而不是 cur = temp; pre = cur; ?
因为我们的目的是进行链表的遍历，实现链表的翻转，如果执行了 cur = temp; pre = cur; 那么 pre 就找不到它的下一个结点了（也就是它右边的第一个结点），指向到了错误的位置，链表不会正常执行的；

5、小结

在进行链表翻转的时候，不需要重新定义一个新的链表进行一些拷贝 *** 作，十分浪费内存，直接使用双指针法的链表翻转，效率高，思路简单；