首页 > 试题广场 > 翻转链表
[编程题]翻转链表

对于一个链表 L: L0→L1→…→Ln-1→Ln,
将其翻转成 L0→Ln→L1→Ln-1→L2→Ln-2→…

输入是一串数字,请将其转换成单链表格式之后,再进行操作


输入描述:
一串数字,用逗号分隔


输出描述:
一串数字,用逗号分隔
示例1

输入

1,2,3,4,5

输出

1,5,2,4,3

备注:
数组长度不超过100000

1个回答

添加回答
看了一下别人的解答都是数组做的。
贴一种效率极低O(n^2)的链表解法,有小伙伴能不能帮忙优化一下
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
 
public c***in {
    public static void main(String[] args) throws IOException {
       BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        while (in.ready()) {
            String[] strings = in.readLine().split("\\,");
            int len = strings.length;
            int[] nums = new int[len];
            for (int i = 0; i < len; i++) {
                nums[i] = Integer.parseInt(strings[i]);
            }
            ListNode dummy = new ListNode(0);
            ListNode head = dummy;
            for (int n : nums) {
                dummy.next = new ListNode(n);
                dummy = dummy.next;
            }
            int i = 0;
            List<Integer> list = new ArrayList<>();
            while (len - 2 * i - 1 >= 0) {
                ListNode t_head = head;
                int count1 = 1 + i;
                while (count1 > 0) {
                    t_head = t_head.next;
                    count1--;
                }
                list.add(t_head.val);
                int count2 = len - 2 * i - 1;
                while (count2 > 0) {
                    t_head = t_head.next;
                    count2--;
                }
                if (len - 2 * i - 1 != 0) {
                    list.add(t_head.val);
                }
                i++;
                // len-2*i
            }
            StringBuilder stringBuilder = new StringBuilder();
            for (int index = 0; index < len; index++) {
                stringBuilder.append(list.get(index));
                if (index != len - 1)
                    stringBuilder.append(",");
            }
            System.out.println(stringBuilder);
        }
        in.close();
    }
}
class ListNode {
    public int val;
    public ListNode next;
 
    public ListNode(int x) {
        val = x;
        this.next = null;
    }
}

编辑于 2019-05-16 21:41:50 回复(2)

热门推荐

通过挑战的用户