算法题--反转链表

https://leetcode-cn.com/problems/reverse-linked-list/

反转链表，递归和循环两种方法。

```java
package com.example.demo.core.Leecode;

/**
 * @author: HanXu
 * on 2022/2/24
 * Class description: 反转链表
 * Head头结点也储存数据（LeeCode这道题的规则）
 */
public class ReversalLinked {

static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        ListNode head = buildLinked(arr);
        printLinked(head);

//        ListNode node = reverLinked(head);
        ListNode node = reverLinked2(head);

printLinked(node);
        /*
        1 2 3 4 
        4 3 2 1 
         */
    }

/**
     * 循环实现，重点是1、记录pre和current；2、先记录next，再反转，再更新pre和current
     * @param currentNode
     * @return
     */
    private static ListNode reverLinked2(ListNode currentNode) {
        ListNode preNode = null;
        while (currentNode != null) {
            //记录当前节点的next，先记录，不然一会next反转就没法记了
            ListNode tempNext = currentNode.next;
            //反转 回指
            currentNode.next = preNode;
            //pre和currentNode更新
            preNode = currentNode;
            currentNode = tempNext;
        }
        return preNode;
    }

/**
     * 反转链表，递归实现，思路是将链表分为：当前节点 和 后面所有节点看成一个节点
     * @param currentNode
     * @return
     */
    private static ListNode reverLinked(ListNode currentNode) {
        if (currentNode == null || currentNode.next == null) {
            return currentNode;
        }
        ListNode bigNode = currentNode.next;
        //这个一路递归到最后一个节点
        ListNode node = reverLinked(bigNode);
        //从最后一个节点一路向回指
        bigNode.next = currentNode;
        //当前节点原本的next断掉，反转后的next会在上一层递归的上一句代码中连接上
        currentNode.next = null;
        //返回最后一个节点
        return node;
    }

/**
     * 打印链表
     * @param head
     */
    private static void printLinked(ListNode head) {
        ListNode pNode = head;
        while (pNode != null) {
            System.out.print(pNode.val + " ");
            pNode = pNode.next;
        }
        System.out.println();
    }

/**
     * 构建链表
     * @param arr
     */
    private static ListNode buildLinked(int[] arr) {
        ListNode head = new ListNode();
        ListNode pNode = head;
        for (int i = 0; i < arr.length; i++) {
            ListNode listNode = new ListNode(arr[i]);
            pNode.next = listNode;
            pNode = pNode.next;
        }
        return head.next;
    }
}
```

算法题--反转链表

文章目录

发表评论