反转链表

2021年09月16日 阅读数:1
这篇文章主要向大家介绍反转链表,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

题目要求,给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。node

本身写的代码,用的遍历法,大致思路就是先设置一个辅助节点,把头结点存起来,headA.next = head;head = headA;算法

方便后续使用。而后定义一个辅助指针,用于后续的变换操做,ListNode temp1 = headA.next; ListNode storage = new ListNode(0);学习

用的迭代法,思路就是把temp1后面的节点拿出来,存储到一个辅助变量里,而后在把temp的下下个节点做为下个节点,把被拿出来并存储的节点放到head节点以后,就完成了一个个的翻转。spa

public ListNode reverseList(ListNode head) {
        ListNode headA = new ListNode(0);
        headA.next = head;
        head = headA;
        ListNode temp1 = headA.next;
        ListNode storage = new ListNode(0);

        //把temp1.next移除,
        //temp1.next = temp.next.next;若temp.next.next为空,则拿掉以后把temp.next置空
        // 存储到storage。
        //把stroage插入headA与temp1之间
     

        while(true) {
            if (headA == null || headA.next == null)
                return null;
            if (temp1.next == null) break;

            storage = temp1.next;

            if(temp1.next.next == null){
                temp1.next = null;
            }
            else{
                temp1.next = temp1.next.next;
            }


            storage.next = headA.next;
            headA.next = storage;


            if (temp1.next == null) break;
        }
        return head.next;
    }

查阅资料发现了更为简洁的算法:指针

public static Node reverseList(Node node) {
    Node pre = null;
    Node next = null;
    while (node != null) {
        next = node.next;
        node.next = pre;
        pre = node;
        node = next;
    }
    return pre;
}

咱们来看这段代码,假设咱们的链表为 1->2->3->4,第一次执行,有:code

next = 1.next;blog

1.next = pre(null);递归

pre = 1;class

node = next(2);变量

第二次执行,有:

next(2) = 2.next;

2.next = pre(1);

pre = 2;

2 = 3;

每次执行,把node向后移了一位,腾出来的指向pre,造成一个新链表,这个新链表就是反转的链表。

递归方式没看懂,学习了栈以后再写。