反转链表

1 从尾到头打印链表内容

问题描述

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

问题分类

  • 线性数据结构
  • 枚举法
  • 排序问题

问题分析

1.1 从尾到头打印链表内容——辅助栈

策略选择

  • 数据结构：链表、栈、数组
  • 算法思想：枚举法
  • 可以利用栈的先进后出特性。

算法设计

  1. 入栈： 遍历链表，将各节点值 push 入栈。（Python​ 使用 append() 方法，​Java​借助 LinkedList 的addLast()方法）。
  2. 出栈： 将各节点值 pop 出栈，存储于数组并返回。（Python​ 直接返回 stack 的倒序列表，Java ​新建一个数组，通过 popLast() 方法将各元素存入数组，实现倒序输出）。

算法分析

  • 时间复杂度O(n)
  • 空间复杂度O(n)

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> reversePrint1(ListNode* head) {
    stack<int> s;
    vector<int> v;
    ListNode * temp=head;
    while(temp){
        s.push(temp->val);
        temp=temp->next;
    }
    while(!s.empty()){
        v.push_back(s.top());
        s.pop();
    }
    return v;
}

1.2 从尾到头打印链表内容——递归法

策略选择

  • 数据结构：链表
  • 算法思想：枚举法
  • 利用递归后续遍历的特性（子节点在父节点之前除了)

算法设计

  1. 递推阶段： 每次传入 head.next ，以 head == None（即走过链表尾部节点）为递归终止条件，此时返回空列表 [] 。
  2. 回溯阶段： 利用 Python 语言特性，递归回溯时每次返回 当前 list + 当前节点值 [head.val] ，即可实现节点的倒序输出。

算法分析

  • 时间复杂度O(n)
  • 空闲复杂度O(n)

算法实现

1
2
3
4
5
6
7
8
9
10
11
vector<int> reversePrint(ListNode* head) {
    vector<int> vec;
    rp(head,vec);
    return vec;
}
void rp(ListNode* head,vector<int>&vec) {
    if(head==nullptr)return ;
    rp(head->next,vec);
    vec.push_back(head->val);
    return ;
}

2 反转链表

问题描述

  • 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
    链接

2.1 反转链表——普通循环反转

策略选择

  • 循环

算法设计

  • 在每次循环的时候。到达一个节点。
    • 记录本节点的下一个节点
    • 记录本节点的上一个几点
    • 反转本次节点指向上一个节点
    • 复制本层节点= 下一个节点。开始下一次循环。

算法分析

  • 时间复杂度O(n)
  • 空间复杂度O(n)

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
ListNode* reverseBetween(ListNode* head, int left, int right) {
    int i=1;
    ListNode* node=head;
    ListNode* last_node=nullptr;
    ListNode* before_left=nullptr;
    if(left==1){
        before_left=new ListNode();
        before_left->next=head;
    }
    ListNode* after_node;
    while(true){
        after_node=node->next;
        if(i==left-1){
            before_left=node;
        }            
        if(i>left && i<=right){
            node->next=last_node;
        }
        if(i==right){
            before_left->next->next = after_node;
            before_left->next=node;
            break;
        }
        last_node=node;
        node=after_node;
        i++;
    }
    if(left==1)return before_left->next;
    return head;
}

2.2 反转链表——头插法反转

策略选择

  • 循环
  • 插入反转

算法设计

  • 每次循环的时候。到达本节点。将本节点的下一个节点插入到左节点前的下一个节点。从left开始
    • temp保留该节点的下一个几点。
    • 当前节点指向下一个节点的下一个节点（删除下一个节点）
    • temp指向左前节点的下一个节点
    • 左前节点指向该节点（插入下一个几点）

算法分析

  • 时间复杂度O(n)
  • 空间复杂度O(1)

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 头插法
    ListNode* reverseBetween2(ListNode* head, int left, int right) {
        ListNode* before_head = new ListNode();
        before_head->next=head;
        ListNode* before_left;
        ListNode* node=before_head;
        ListNode* temp;
        for(int i=0;i<=right;i++){
            if(i==left-1)before_left=node;
            if(i>=left && i<right){
                temp = node->next;
                node->next = temp->next;
                temp->next=before_left->next;
                before_left->next=temp;
            }
            else{
                node=node->next;
            }
        }
        return before_head->next;
    }

链表反转——递归法

策略选择

  • 递归法
  • 等价于使用栈保存了节点的路径。不会在反转后回不到过去的节点

算法设计

  • 递归

    • 当到右节点，使用全局变量记录右节点和右节点的下一个节点。
    • 当在左右之间时，直接使自身的下一个节点指向自己。
    • 当到达左节点时。与有节点和有节点的下一个反转。

  • 递归的参数

  • 递归的返回值

  • 递归的执行

  • 递归的终止条件

  • 递归前的处理和递归后的处理。

算法分析

  • 时间复杂度O(n)
  • 空间复杂度O(n)

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 递归法，把它当做只有一侧的树。后续遍历。取得时候将节点路径放到栈里。回来的时候直接反转也能返回最初的节点。
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* before_head = new ListNode();
        before_head->next=head;
        dfs(before_head,left,right,0);
        return before_head->next;
    }
    ListNode* right;
    ListNode* right_next;
    void dfs(ListNode* head,int left,int right,int i){
        if(i>right)return ;
        // cout<<i<<endl;
        dfs(head->next,left,right,i+1);
        if(i>=left && i<right){
            head->next->next=head;//下一个节点指向自己
        }
        if(i==right){
            this->right=head;
            this->right_next=head->next;
            // cout<<head->val<<"feji"<<endl;
            
        }
        if(i==left-1){
            head->next->next=this->right_next;
            head->next=this->right;
        }
        return ;
    }