反转链表相关的问题

来源：5-6 链表与双指针 Remove Nth Node Form End of List

qq_往事_8

2019-10-07

老师，我在做题中遇到了这样一道题，要求输入索引x，返回倒数第x个位置的元素，这里我想是需要用反转链表的方式来做然后在将节点的值添加到ArrayList中通过下标返回。
我看了之前视频讲解中反转链表的代码，那里是将cur设置为ListNode类型，可是这道题只能传入索引，在这里应该怎么为cur进行赋值，反转完成后怎么将引用赋值给LinkedList啊
图片描述
这是我写的，运行不了，不知道怎么才能将元素添加到ArrayList，说说思路呗

public int printListNodeValue(int index){
        LinkedList<ListNode> linkedList = new LinkedList<>();
        for (int i = 1; i < 8; i++) {
            linkedList.add(new ListNode(i));
        }

        ListNode pre = null;
        ListNode cur = linkedList.getFirst();
        ArrayList<Integer> arrayList = new ArrayList<>();

        while (cur != null){
            ListNode next = cur.next;

            cur.next = pre;

            pre = cur;
            cur = next;
            arrayList.add(linkedList.removeFirst().val);
        }

        return arrayList.get(index-1);
    }

写回答

2回答

qq_往事_8

提问者

2019-10-08

import java.util.ArrayList;

public class Solution {
    public class ListNode {
        int val;
        ListNode next;

        public ListNode(int x) {
            this.val = x;
        }

        public ListNode(int[] arr) {
            if (arr == null || arr.length == 0) {
                throw new IllegalArgumentException("arr can not be empty.");
            }
            this.val = arr[0];
            ListNode curNode = this;
            for (int i = 1; i < arr.length; i++) {
                curNode.next = new ListNode(arr[i]);
                curNode = curNode.next;
            }
        }

        @Override
        public String toString() {
            StringBuilder s = new StringBuilder("");
            ListNode curNode = this;
            while (curNode != null) {
                s.append(Integer.toString(curNode.val));
                s.append(" -> ");
                curNode = curNode.next;
            }
            s.append("NULL");
            return s.toString();
        }
    }

    private ListNode createLinkedList(int[] nums){
        ListNode dummy = new ListNode(0);
        ListNode pre = dummy, cur = null;
        for (int i = 0; i < nums.length; i++) {
            cur = new ListNode(nums[i]);
            pre.next = cur;
            pre = cur;
        }
        return dummy.next;
    }

    public int printListNodeValue(int index) {
        int[] nums = {1,2,3,4,5,6,7};
        ListNode root = createLinkedList(nums);

        ListNode pre = null;
        ListNode cur = root;
        while (cur != null){
            ListNode next = cur.next;

            cur.next = pre;

            pre = cur;
            cur = next;
        }

        ArrayList<Integer> res = new ArrayList<>();
        while (pre != null){
            res.add(pre.val);
            pre = pre.next;
        }

        return res.get(index-1);
    }

    public static void main(String[] args) {
        int i = new Solution().printListNodeValue(1);
        System.out.println(i);
    }
}

//img1.sycdn.imooc.com/szimg/5d9be585098eea9704550200.jpg

liuyubobobo

2019-10-07

你的代码里只是 new ListNode(i)，每一个 ListNode 的 next 没有赋值。所以，while 循环中每一个 cur.next 都是空的。单步跟踪调试看一看是不是这样？

实际上，LinkedList 内部隐藏了链表的实现。从用户的角度看只是容器。你将一个一个 ListNode 扔进 LinkedList，这些 ListNode 没有连起来，是分散的。你的代码没有构建出链表。构建链表的方式可以参考 5-2 小节，或者我的《玩转数据结构》课程，有系统讲链表。https://coding.imooc.com/class/207.html

如果正确构建出链表，按照你的思路，只需要：

1）翻转链表；

2）遍历链表，将链表中的每个元素放进 ArrayList

3）返回相应索引的元素。

加油！：）

qq_往事_8

都能计算出正确结果，怎么还不行啊

2019-10-08

共2条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7410 学习 · 1150 问题