首页 > 试题广场 >

链表翻转

[编程题]链表翻转
  • 热度指数:265 时间限制: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,点此查看相关信息
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)