反转链表

发表于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

LeetCode题目，206. Reverse Linked List

先看题目描述

BApe8s.png

大意就是给定一个链表，让我们将链表反转

算法和思路

迭代

在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。最后要返回新的头引用

递归

思路就是实现一个递归函数可以反转链表，假设头节点下的所有节点都已经反转好了，现在就剩头节点和其 next 节点 没有完成最后的反转了，然后就反转一下头节点和其 next 节点；执行 head.next.next = head，head.next = null，注意最后返回的是新的头节点

算法源码

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 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 cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode res = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return res;
    }
}