链表翻转

[编程题]链表翻转

热度指数：274 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

将一个给定的单链表反转，例：1-2-3-4-5，反转为5-4-3-2-1

示例1

输入

{1,2,3,4,5}

输出

{5,4,3,2,1}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

wonderson

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode reverseList (ListNode head) {
       ListNode pre = null, post = head, tmp;
        while (post != null) {
            tmp = post.next;
            post.next = pre;
            pre = post;
            post = tmp;
        }
        return pre;
    }
}

发表于 2022-03-09 14:15:52 回复(0)

阿邱

使用头插法解决此问题，每次新插入的节点都放在最前面，以此实现翻转链表。

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode reverseList (ListNode head) {
        // write code here
        ListNode dummyHead = new ListNode(0);
        ListNode tail = null;
        dummyHead.next = tail;
        // 采用头插法解决此问题
        while(head != null){
            ListNode node = new ListNode(head.val);
            node.next = dummyHead.next;
            dummyHead.next = node;
            head = head.next;
        }
        return dummyHead.next;
    }
}

发表于 2021-09-11 17:24:59 回复(0)