HOME/剑指Offer/

反转单向和双向链表

Article Outline
TOC
Collection Outline

反转单向和双向链表

【题目】 分别实现反转单向链表和反转双向链表的函数。 【要求】 如果链表长度为N,时间复杂度要求为O(N),额外空间复杂度要求为O(1)

图解 现在有一个单向链表如下图所示: 正向链表

反转后如下所示: 反向链表

接下来解析反转函数: 反转单向链表1 第一步:next = head.next 将 head.next 赋值给 next 变量,也就是说 next 指向了节点2,先将节点2 保存起来。

第二步:head.next = pre 将 pre 变量赋值给 head.next,即 节点1 指向了 null

第三步:pre = head

将 head 赋值给了 pre,即 pre 指向节点1,将节点1 设为“上一个节点”

第四步:head = next

将 next 赋值给 head,即 head 指向了节点2。将节点2 设为“头节点”

第一次循环完毕,进入第二次循环,如下图 反转单向链表2 第一步:next = head.next 将 head.next 赋值给 next 变量,也就是 next 指向了节点3,先将节点3 保存起来。

第二步:head.next = pre 将 pre 赋值给 head.next,pre 在上一次循环的时候指向了节点1,那么这一步的意义就是节点2 指向了 节点1,完成一次反转

第三步:pre = head

将 head 赋值给了 pre,即 pre 指向节点2,将节点2 设为“上一个节点”

第四步:head = next

将 next 赋值给 head,即 head 指向了节点3。将节点3 设为“头节点”

第二次循环完毕,以此类推!第三次第四次第五次循环。最后反转成如下图 完成反转

总结 保存当前头节点的下一个节点(当前头节点为2,先将节点3 保存起来)

将当前头节点的下一个节点指向 “上一个节点”(当前头节点2 指向了 (“上一个节点”)节点1),这一步才是实现反转

将当前头节点设置 “上一个节点”(将节点2 设为“上一个节点”)

将保存的下一个节点设置 “头节点”(将节点3 设为“头节点”)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}


    public class DoubleNode {
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int data) {
            this.value = data;
        }
    }

    // 反转双向链表
    public DoubleNode reverseList(DoubleNode head) {
        DoubleNode pre = null;
        DoubleNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return pre;
    }