单链表反转

发表于 | 分类于
字数统计: 534 | 阅读时长 ≈ 2

单链表反转

题目说明

LeetCode第206题.

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list

解题思路

利用外部空间

看到题目,最简单的想法就是.将链表中的元素迭代放入一个数组.或者链表或者Stack中.然后再迭代一遍.

将ListNode中的元素更改为容器中的元素即可.

例如:

1
2
3
1->2->3->4->5
第一步: 遍历节点.将元素放入栈中{1,2,3,4,5};
第二部: 再次遍历元素.每遍历一个元素,从栈顶弹出一个值.然后修改节点的值.

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ListNode reverseList(ListNode head) {
         if(head == null) return head;
        Stack<Integer> stack = new Stack<>();
        ListNode node = head;
        while(node != null){
            stack.add(node.val);
            node = node.next;
        }
        node = head;
        while(node != null){
            node.val = stack.pop();
            node = node.next;
        }
        return head;
    }

这样,就完成了单链表反转.当然,我们也可以不改变原节点的值.直接创建一个新节点也是可以的.这里就不演示了.

双指针迭代

我们可以使用两个指针,一个Pre 指向反转之后的节点.最初是指向Null.

另一个cur,表示当前待反转的节点.

每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
当迭代结束时(cur==null),pre就是最后一个节点了.

如下动图:

单链表反转

根据上述思路,实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
public ListNode reverseList(ListNode head) {
       ListNode prev = null;
       ListNode curr = head;
       while (curr != null) {
           ListNode nextTemp = curr.next;
           curr.next = prev;
           prev = curr;
           curr = nextTemp;
       }
       return prev;
   }

递归

递归的思路和上面动图差不多,只不过是实现方式有点差别.

代码如下:

1
2
3
4
5
6
7
8
9
10
public ListNode reverseList(ListNode head) {
        return reverse(null,head);
    }

    private static ListNode reverse(ListNode pre,ListNode cur){
        if(cur==null) return pre;
        ListNode next = cur.next;
        cur.next = pre;
        return reverse(cur,next);
    }
0%