leetcode-反转链表

刷leetcode第二十四题"反转链表"，以下为解题过程

题目描述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

题目解析

1. 直接使用递归进行反转

2. 使用双指针迭代交换

3. 使用栈结构特性进行交换

4. 使用双链表进行更新反转链表

注意

1. 递归会形成闭环，要解除闭环情况
2. 双指针要注意其迭代条件，右指针遍历到末尾
3. 栈结构压栈弹栈，后面要将其进行串联
4. 双链表注意每次指针的指向

具体代码实现

第一种方法递归

public ListNode reverseList(ListNode head) {
    // 使用递归解决
    // 终止条件
    if (head == null || head.next == null) {
        return head;
    }
    // 递归过程
    ListNode node = reverseList(head.next);
    // 反转过程(闭环)
    head.next.next = head;
    // 去环操作
    head.next = null;
    return node;
}

第二种方法双指针

public ListNode reverseList2(ListNode head) {
    // 使用双指针进行反转
    // 终止条件
    if (head == null || head.next == null) {
        return head;
    }
    ListNode left = null;
    ListNode right = head;
    // 进行交换
    while (right != null){
        ListNode t = right.next;
        right.next = left;
        left = right;
        right = t;
    }
    return left;
}

第三种方法栈结构

public ListNode reverseList3(ListNode head) {
    // 使用栈进行链表的反转
    Stack<ListNode> stack = new Stack<>();
    // 存入栈中
    while (head!= null){
        stack.push(head);
        head = head.next;
    }
    // 弹出栈中
    ListNode node = stack.pop();
    while (!stack.isEmpty()){
        // 交换，为了弹出前面k个值
        ListNode tmp = stack.pop();
        node.next = tmp;
        node = node.next;
    }
    node.next = null;
    return node;
}

第四种方法双链表

public ListNode reverseList4(ListNode head) {
    // 使用双链表进行更新反转链表
    ListNode newNode = null;
    while (head != null){
        // 存储下一个节点的位置，进行遍历
        ListNode tmp = head.next;
        // 将头节点赋值新链表值
        head.next = newNode;
        // 将节点赋值到新链表上
        newNode = head;
        // 重新赋值遍历
        head = tmp;
    }
    return newNode;
}