反转链表

题目描述

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

思路

第一种思路

反转链表意思就是说A->B->C->D反转称为D->C->B->A,

• 定义一个新head头指针，标记为newHead，将它初始为NULL，并非指向NULL，最后我们选择返回这个newHead指针作为新链表的头指针。
• 定义一个结点node作为”临时中转站”，初始化与否并无大影响。
• 进行循环遍历链表各个结点，判定head指针是否为空，即是否到达了原链表的结尾。如果不为空，说明还没有到达尾部。如果程序第一次运行就没有进入循环，说明传入了一个空链表，此时返回newHead新链表的头指针，同样返回NULL，这样处理也是合理的。
• 以下开始逆序链表逻辑：在当前指针不为NULL时，先对原链表做头删操作，再对新链表做头插操作。即使用循环进行操作：
• 让node指针指向传入函数链表的头指针head，两指针指向保持相同。
• 然后让head指针指向它的next结点，此时旧链表已经完成了头删操作。第一个结点已经被”切割”下来。接下来要做的就是对新链表进行头插操作，使结点放入新链表。
• 让node指针的next下一个结点指向新链表的头指针newHead，完成结点的链接，即头插入新的链表中。然后更新newHead指向为新链表的头结点。进行下一次循环。
• 最终head指针指向了原链表的结尾，即为NULL，退出循环，此时新链表已经反转完毕。
• 最终返回新链表头指针newHead即可。

第二种思路

• 利用选择语句，找到空链表的情况，此情况返回NULL空指针，因为空链表不能反转，或者说反转之后还是一个空链表，返回空。
• 利用三个指针p0”前指针”、p1“当前指针”、p2”后指针”来分批处理链表元素，p0置为NULL，它将作为链表的尾结点向前推进处理，p1指向旧链表的头指针head，p2指向旧链表的头指针的next结点。
• 开始遍历链表，循环判定因子为p1，当它为空时到达链表尾部跳出循环。否则在表中执行循环内逻辑：将p1指向的当前结点的下一个结点指向p0，即前一个结点。
  此时p0为NULL，那么p1的下一个结点就为空了，它现在是最后一个结点。
• 然后将p0指针指向p1，将p1指针指向p2，注意这两步不可以调换顺序，否则正确向后挪移一位。此时完成了三个指针的一轮更迭。
• 判定p2指针是否为空，如果为空说明此时p2到达了链表结尾，当前指针p1的指向为最后一个结点，它的next即为空。如果不为空，将p2更新到下一个结点，进行下一次循环。
• 下一次进行循环时，就会把截断结点链接到新链表的头部，同时更新三个指针。继续循环。
• 循环终止条件为：p1指向了链表尾部的NULL，此时p1的前指针p0即指向了反转后的链表，它就是新链表的head头指针。此时返回p0即可。

代码实现

第一种思路

public class Main {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        ListNode a = ReverseList(listNode1);
    }
    public static ListNode ReverseList(ListNode head) {
        if(head == null) return null;
        ListNode newhead = null;//新的头指针
        ListNode temp = null;//中转指针
        while (head!=null)
        {
            //这样把链表头去掉
            temp = head;
            head = head.next;
            //新链表,temp指向的是链表的下一个，hewhead其实还是上一个，所以先把temp的next指向上一个，然后再把temp指向newhead
            temp.next = newhead;
            newhead = temp;

        }
        return newhead;
    }
}
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

第二种思路

public class Main {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        ListNode a = ReverseList(listNode1);
    }
    public static ListNode ReverseList(ListNode head) {
        if(head == null) return null;
        ListNode p0 = null;
        ListNode p1 = head;
        ListNode p2 = head.next;
        while (p1 !=null)
        {
            p1.next = p0;
            p0 = p1;
            p1 = p2;
            if(p2!=null)
            {
                p2=p2.next;
            }
        }
        return p0;
    }
}
class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}