反转链表相关的问题

Question

老师，我在做题中遇到了这样一道题，要求输入索引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);
    }

Answer 1

提问者 qq_往事_8 2019-10-08 09:25:27

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);
    }
}

Answer 2

liuyubobobo 2019-10-07 11:26:22

 你的代码里只是 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 #1

  现在链表能连在一起了，我在ide中测试也能得到正确的结果，但是往牛客网上提交却出现了这个问题，

• 提问者 qq_往事_8 #2

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