[数据结构与算法]剑指Offer 24 反转链表

剑指Offer 24 反转链表

题目描述：

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。LeetCode链接

迭代法

定义三个指针

• 第一个指针prev，指向当前节点的前一个元素，最初是指向 NULL。

• 第二个指针 cur ，最初指向 head。

• 第三个指针为了保存cur的下一个节点，防止cur指向prev后造成断链。

由于三变量演示图示过于密集，所以动画上只引入两个变量。

 public ListNode reverseList(ListNode head)
    {
        //定义三个指针，分别保存当
        ListNode prev = null;//前节点的前驱结点 初始化为null
        ListNode cur = head;//当前节点 初始化为头节点
        ListNode next;//当前节点的后继节点，初始化为null
        //如果当前节点不为空，就循环，使得三个指针向前移动
        while (cur != null)
        {
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        //循环结束后，prev就是反转后的头节点
        return prev;
    }

头插法

定义三个指针

• 第一个指针newHead，指向新链表的头节点，最初指向 NULL。

• 第二个指针 cur ，最初指向原始链表头节点head。

• 第三个指针为了保存cur的下一个节点，防止cur指向prev后造成断链。

  

 public ListNode reverseList(ListNode head)
    {
        //同样定义三个指针
        ListNode newHead = null;//新的头节点
        ListNode cur = head;//当前节点，初始为头节点
        ListNode next;//当前节点的后继节点
        while (cur != null)
        {
            next = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = next;
        }
        return newHead;
    }