首页 > 试题广场 >

翻转链表

[编程题]翻转链表
  • 热度指数:5685 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

对于一个链表 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
48 ms 10408K Python 3
s = input().split(',')
t = len(s)
r = t//2
o = []

def f(a): 
    x,y = s[:r],s[r+a:][::-1] # 拆分翻转
    for i in range(r):
        o.extend([x[i],y[i]])
    if a: o.append(s[r])

if t%2 == 1: f(1)
else: f(0)

print(','.join(o))

65 ms 9740K Python 3
s = input().split(',')
t = len(s)
d = t // 2
o = []

for i in range(d):
    o.extend([s[i],s[-i-1]])

if 2*d != t:
    o.append(s[d])

print(','.join(o))

769 ms 9412K Python 3
a = input().split(',')
# 反复横跳
c = [a.pop(-1) if i%2==1 else a.pop(0) for i in range(len(a))]
print(','.join(c))
编辑于 2019-11-02 03:09:47 回复(0)
class solution(object):   
    def function(self, a:int, s: list):
        x, y = s[:r], s[r+a:][::-1]
        for i in range(r):
            res.extend([x[i], y[i]])
        if a:
            res.append(s[r])
        return res
    
if __name__ == "__main__" :
    s = input().split(",")
    t = len(s)
    r = t // 2
    res = []
    q = solution() 
    if t%2==1:
        q.function(1, s)
    else:
        q.function(0, s)
    print(",".join(res))
    
发表于 2022-03-09 11:22:14 回复(0)
#整体思路是:
#先根据输入初始化成一个单链表
#然后复制一个刚生成的链表
#把其中一个链表进行反转
#按照链表长度的一半次数合并两个链表,即可生成题目要求的链表
class Node(object):
    def __init__(self,val):
        self.val = val
        self.next = None
class ClainList(object):
    #初始化列表
    def __init__(self,list):
        self.count = 0
        if not list:
            return None
        self.head = None
        cur = None
        for i in list:
            if cur == None:
                self.head = Node(i)
                cur = self.head
            else:
                temp = Node(i)
                cur.next = temp
                cur = temp
            self.count += 1
    def reverse(self,head):
        #反转链表
        if not head:
            return None
        pre = head
        if head.next == None:
            return head
        cur = head.next
        head.next = None
        if cur.next == None:
            cur.next = pre
            return cur
        post = cur.next
        while cur!=None:
            cur.next = pre
            if post == None:
                break
            pre = cur
            cur = post
            post=post.next
        return cur
    def series(self,head):
        #把链表以字符串形式输出
        res = []
        cur = head
        while cur:
            res.append(cur.val)
            cur = cur.next
        print(','.join(map(str,res)))
    def copy(self,head):
        #复制一个新的链表
        if not head:
            return None
        new_head = Node(head.val)
        cur1 = head
        cur2 = new_head
        while cur1:
            cur1 = cur1.next
            if cur1:
                temp = Node(cur1.val)
            else:
                temp = None
            cur2.next = temp
            cur2 = temp
        return new_head
    def combine(self,head1,head2,n):
        #把两个顺序相反的链表合并成题目要求
        if not head1 and not head2:
            return None
        cur1 = head1
        cur2 = head2
        post1 = head1.next
        post2 = head2.next
        new_cur = None
        new_head = None
        c = n//2
        for i in range(c):
            if new_head == None:
                new_head = cur1
                new_cur = cur1
            else:
                new_cur.next = cur1
                new_cur = new_cur.next
            new_cur.next = cur2
            new_cur = new_cur.next
            cur1 = post1
            cur2 = post2
            if not post1&nbs***bsp;not post2:
                break
            post1 = post1.next
            post2 = post2.next
        if n == 1:
            new_head = new_cur = head1
        elif n%2 == 1:
            new_cur.next = cur1
            new_cur = cur1
        new_cur.next = None
        return new_head
def main():
    array = map(int,input().split(','))
    s = ClainList(array)
    n = s.count
    head1 = s.copy(s.head)
    head2 = s.reverse(s.head)
    res = s.combine(head1,head2,n)
    s.series(res)
main()

发表于 2019-12-03 21:46:17 回复(0)
//先用快慢指针拆分链表,翻转后半部分,再和前半部分拼接;
#include <bits/stdc++.h>
using namespace std;
struct node{
    int data;
    node* next;
};

node* creatlist(vector<int> &arr){
    node *head,*cur;
    if(arr.empty())
        return nullptr;
    head=new node;
    head->data=arr[0];
    head->next=nullptr;
    cur=head;
    for(int i=1;i<arr.size();i++){
        node *pre=cur;
        cur=new node;
        cur->data=arr[i];
        cur->next=nullptr;
        pre->next=cur;
    }
    return head;
}
node* reverse(node *head){
    if(head==nullptr)
        return head;
    node *cur,*pre,*next;
    cur=head->next;
    pre=head;
    pre->next=nullptr;
    while(cur){
        next=cur->next;
        cur->next=pre;
        pre=cur;
        cur=next;
    }
    return pre;
}

node* solve(node* head){
    node *slow,*fast;
    slow=fast=head;
    while(fast->next){
        slow=slow->next;
        fast=fast->next;
        if(fast->next)
            fast=fast->next;
    }
    node *rehead=reverse(slow->next);
    slow->next=nullptr;
    node *cur=head,*next1,*next2;
    while(cur&&rehead){
        next1=cur->next;
        cur->next=rehead;
        next2=rehead->next;
        rehead->next=next1;
        rehead=next2;
        cur=next1;
    }
    return head;
}
int main(){
    vector<int> arr;
    while(1){
        int t;
        cin>>t;
        arr.push_back(t);
        if(cin.get()=='\n')
            break;
    }
    node * head=creatlist(arr);
    head=solve(head);
        while(head){
            cout<<head->data;
            head=head->next;
            if(head)
                cout<<",";
        }
    return 0;
}

发表于 2019-10-19 12:24:19 回复(0)
while(line = readline()){
    var lines = line.split(",");
    var len = lines.length;
    var temp = [];
    if(len%2==0){
        for(i=0;i<len/2;i++){
           temp.push(lines[i]);
           temp.push(lines[len-i-1]);
        }
                 print(temp)
    }else{
            for(i=0;i<(len-1)/2;i++){
                temp.push(lines[i]);
                temp.push(lines[len-i-1]);
        }
        temp.push(lines[(len-1)/2]);
         print(temp)
    }

}

发表于 2019-09-03 13:14:56 回复(1)
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int num;
    char charset;
    vector<int> arr;
    while(cin>>num>>charset)
        arr.push_back(num);
    cin>>num;
    arr.push_back(num);
    cout<<arr[0];
    int i=1,j=arr.size()-1;
    while(i<j)
    {
        cout<<","<<arr[j]<<","<<arr[i];
        i++;
        j--;
    }
    if(i==j)
        cout<<","<<arr[j]<<endl;
    return 0;
}

发表于 2019-08-14 21:51:54 回复(1)
class Node:
    def __init__(self, x):
        self.val = x
        self.next = None

num = list(map(int, input().split(',')))
node = Node(-1)
temp = node
for i in num:
    temp.next = Node(i)
    temp = temp.next
res = []
nod = node.next
while nod:
    res.append(nod.val)
    nod = nod.next

ans = ""
l = len(res)
for i in range(l):
    if i%2 == 0:
        ans += str(res.pop(0)) + ','
    else:
        ans += str(res.pop()) + ','
print(ans[:len(ans)-1])


编辑于 2019-07-31 13:33:14 回复(0)
看到好多用数组做的,这属于投机取巧,面试时是会被怼的。人家要求用链表就老老实实使用链表呗。
import java.util.Scanner;

public class reverse_lists {
    public void reverse_lists(){
        //创建一个链表
        Scanner sc = new Scanner(System.in);
        String string = sc.nextLine();
        String[] chars = string.split(",");
        ListNode list = new ListNode(Integer.parseInt(String.valueOf(chars[0])));

        //创建两个快慢指针,一次遍历找到链表的中间节点
        ListNode p = list;
        for(int i = 1;i<chars.length;i++){
            p.next = new ListNode(Integer.parseInt(String.valueOf(chars[i])));
            p = p.next;
        }
        p = list;
        ListNode q = list;
        while (q.next!=null && q.next.next!=null){
            p = p.next;
            q = q.next.next;
        }
        q = p.next;
        p.next = null;
        p = list;

        //将链表的后半段进行反转,如(4->5)变成了(5->4)
        ListNode newhead = reverse(q);


        //创建一个新的头结点head,让newhead指向它,
        // 然后循环让newhead指向链表的前半段和后半段
        ListNode head = new ListNode(0);
        ListNode newhead1 = head;

        while (p!=null){
                newhead1.next = p;
                p = p.next;
            newhead1 = newhead1.next;
            if(newhead!=null){
                newhead1.next = newhead;
                newhead = newhead.next;
                newhead1 = newhead1.next;
            }
        }
        //注意,这里有将链表头去掉,因为它指向的节点值为0;
        head = head.next;
        StringBuilder res = new StringBuilder();
        //使用字符串输出
        while (head!=null) {
            res.append(head.val).append(",");
            head = head.next;
        }
        System.out.println(res.substring(0,res.length()-1));

    }

    //反转链表
    private ListNode reverse(ListNode head) {
        ListNode curnode = head;
        ListNode pre = null;
        ListNode newhead = null;
        while (curnode!=null){
            ListNode next = curnode.next;
            if(next==null){
                newhead = curnode;
            }
            curnode.next = pre;
            pre = curnode;
            curnode = next;
        }
        return newhead;
    }

    public static void main(String[] args) {
        new reverse_lists().reverse_lists();
    }
}



发表于 2020-06-01 13:51:32 回复(0)
package bilibili;

import java.util.Scanner;

public class 翻转链表 {

	public static void main(String[] args) {
	 
		Scanner sc = new Scanner(System.in);
		
		while(sc.hasNext()) {
			String s = sc.next();
			
			String[] sarr = s.split(",");
		 
			StringBuilder res = new StringBuilder();
			int i = 1;
			int j = sarr.length-1;
	 
			res.append(sarr[0]).append(",");
			 
			while(i<= j) {
				
				res.append(sarr[j]).append(","); 
				if(i+1>j) {
					break;
				}
				res.append(sarr[i]).append(","); 
				i++;
				j--;
			}
		 
			System.out.println(res.substring(0, res.length()-1));
			 
		}
	}

}

直接用数组水过了哈哈哈,,,定义一个尾指针和头指针,然后每次循环往前走一步。
发表于 2020-03-26 22:01:10 回复(1)
import java.util.Scanner;

/*
题目描述:对于一个链表 L: L0→L1→…→Ln-1→Ln,将其翻转成 L0→Ln→L1→Ln-1→L2→Ln-2→…
输入1,2,3,4,5     输出1,5,2,4,3
备注:数组长度不超过100000
 */
public class Main {
    //定义Node节点
    static class ListNode {
        int val;
        ListNode next = null;

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

    public static void main(String[] args) {
        //1.获取控制台输入的信息
        Scanner scanner = new Scanner(System.in);
        String string = scanner.nextLine();
        String[] strings = string.split(",");
        //2.将输入的字符串构成带头节点的2个链表
        ListNode head = creatList(strings);
        reorderList(head.next);
        head = head.next;
        //3.输出
        while(head!=null){
            if(head.next==null){
                System.out.print(head.val);
            }else{
                 System.out.print(head.val+",");
            }
            head=head.next;
        }

    }



    /*
     * 将str创建带头结点的单链表
     */
    public static ListNode creatList(String[] strings) {
        ListNode head = new ListNode(0);
        ListNode tail = head;
        for (String str : strings) {
            ListNode newNode = new ListNode(Integer.valueOf(str));
            tail.next = newNode;
            tail = newNode;
        }
        return head;
    }


    /*
     * 思路:链表平均拆分,后半部分链表反转,在将两个链表合并
     */
    public static void reorderList(ListNode head) {
        if (head == null || head.next == null) return;

        ListNode p1 = head;
        ListNode p2 = head;

        // 找到链表的一半
        while (p2.next != null && p2.next.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }

        // 将链表分为两段
        p2 = p1.next;
        p1.next = null;
        p1 = head;

        // 将后半段进行链表的翻转
        ListNode head2 = p2;
        ListNode next2;
        while (p2.next != null) {
            next2 = p2.next;
            p2.next = next2.next;
            next2.next = head2;
            head2 = next2;
        }
        p2 = head2;

        // 两条链表进行合并
        ListNode next1;
        while (p2 != null) {
            next1 = p1.next;
            next2 = p2.next;

            p1.next = p2;
            p2.next = next1;

            p1 = next1;
            p2 = next2;
        }

    }

}



编辑于 2019-09-11 13:09:14 回复(0)
正经的链表做***被当成傻子吗?
#include <bits/stdc++.h>
using namespace std;

struct node {
    int val;
    node* next;
    node(int x): val(x), next(nullptr){}
};

node* getMid(node* head){
    node* slow = head;
    node* fast = head;
    while(fast != nullptr && fast->next != nullptr){
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

node* reverse(node* head){
    node* pre = nullptr;
    node* curr = head;
    while(curr != nullptr){
        node* tmp = curr->next;
        curr->next = pre;
        pre = curr;
        curr = tmp;
    }
    return pre;
}

void print(node* curr){
    bool flag = true;
    while(curr != nullptr){
        if(flag){
            cout << curr->val;
            flag = false;
        }else{
            cout << "," << curr->val;
        }
        curr = curr->next;
    }
    cout << endl;
}

node* merge(node* l1, node* l2){
    node* dummy = new node(0);
    node* curr =dummy;
    while(l1 != nullptr && l2 != nullptr){
        curr->next = l1;
        curr = l1;
        l1 = l1->next;
        curr->next = l2;
        curr = l2;
        l2 = l2->next;
    }
    if(l1 != nullptr){
        curr->next = l1;
    }
    if(l2 != nullptr){
        curr->next = l2;
    }

    return dummy->next;
}

int main(){
    string s;
    string st;
    cin >> s;

    node* dummy = new node(2);
    node* curr = dummy;

    for(int i = 0; i < s.length(); i++){
        st = "";
        while(i < s.length() && s[i] != ','){
            st.push_back(s[i]);
            i++;
        }
        int num = stoi(st);
        node* nt = new node(num);
        curr->next = nt;
        curr = nt;
    }

    node* l1 = dummy->next;
    node* mid = getMid(l1);
    node* l2 = mid->next;
    mid->next = nullptr;
    l2 = reverse(l2);

    curr = merge(l1, l2);
    print(curr);

}


发表于 2019-08-19 17:49:21 回复(4)
说一下我的思路  首先是分别拿到正向和反向的单链表 如
L0 L1 L2 L3 ... Ln
Ln Ln-1 Ln-2 ...L1  然后进行一个个的合并(比合并链表那题要简单) 
然后在遍历合并后的链表,在长度为n出断开就可以了
发表于 2019-09-05 10:16:34 回复(0)
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <errno.h>

#define OK 1
#define ERROR -1
#define MEMORY_OVERFLOW -2

#define not !

#define DEFAULT_CAPACITY 8
#define InitStack(S) __InitStack(S, DEFAULT_CAPACITY)

typedef int Status;
typedef int ElemType;

typedef struct ListNode {
  ElemType data;
  struct ListNode* next;
} ListNode;

// ==================== 顺序栈的存储结构表示与实现 =================
typedef ListNode* SElemType;

typedef struct {
  SElemType* base;
  SElemType* top;
  size_t capacity; // size_t == unsigned int
} SqStack;

Status __InitStack(SqStack* S, int initialCapacity) {
  if (initialCapacity < 1) {
    printf("InitStack ERROR: The initialCapacity %d Must be > 0!", initialCapacity);
    return ERROR;
  }
  if (!(S->base = (SElemType*) malloc(initialCapacity * sizeof(SElemType)))) {
    printf("InitStack Memory Overflow: %s\n", strerror(errno)); // no enough space!
    exit(MEMORY_OVERFLOW);
  }
  S->top = S->base;
  S->capacity = initialCapacity;
  return OK;
}

bool StackEmpty(SqStack* S) {
  return (*S).top == (*S).base;
}

bool StackFull(SqStack* S) {
  return (S->top - S->base) == (*S).capacity;
}

size_t StackLength(SqStack* S) {
  return (*S).top - (*S).base;
}

void __large_capacity(SqStack* S) {
  if (!(S->base = (SElemType) realloc(S->base, (S->capacity << 1) * sizeof(SElemType)))) {
    printf("__large_capacity Memory Overflow: %s\n", strerror(errno)); // no enough space!
    exit(MEMORY_OVERFLOW);
  }
  S->top = S->base + S->capacity;
  S->capacity <<= 1;
}

Status Push(SqStack* S, SElemType e) {
  if (StackFull(S))
    __large_capacity(S);
  *S->top++ = e;
  return OK;
}

Status Pop(SqStack* S, SElemType* ret) {
  if (StackEmpty(S)) {
    puts("Pop ERROR: The stack is empty!");
    return ERROR;
  }
  *ret = *--S->top;
  return OK;
}

Status DestroyStack(SqStack* S) {
  free((*S).base);
  (*S).top = NULL;
  return OK;
}
// ==================== 顺序栈的存储结构表示与实现 =================


// ==================== function declaration =================
ListNode* createLinkedList(void);
void printLinkedList(ListNode* head);
// ==================== function declaration =================

int main(const int argc, const char** argv)
{
  SqStack S;
  InitStack(&S);
  
  ListNode *head = createLinkedList(),
           *slow = head, *fast = head,
           *p, *q, *nxt;
  
  while (fast && fast->next) {
    Push(&S, slow);
    slow = slow->next;
    fast = fast->next->next;
  }
  
  q = slow;
  if (fast) q = q->next;
  
  while (not StackEmpty(&S)) {
    Pop(&S, &p);
    nxt = q->next;
    q->next = p->next;
    p->next = q;
    q = nxt;
  }
    
  slow->next = NULL;
  printLinkedList(head);
  return 0;
}

ListNode* createLinkedList(void) {
  ListNode dummy = {0, 0},
           *tail = &dummy;
  
  char tmp[(int) 5E5];
  gets(tmp);
  
  char* tok = strtok(tmp, ",");
  while (tok) {
    tail = (*tail).next = calloc(0x0001, sizeof(ListNode));
    (*tail).data = atoi(tok);
    tok = strtok(NULL, ",");
  }
  
  return dummy.next;
}

void printLinkedList(ListNode* head) {
  const ListNode* p;
  for (p = head; p; p = p->next) {
    printf("%d", (*p).data);
    if ((*p).next) putchar(',');
  }
}

发表于 2021-07-06 10:27:25 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    string S, s;
    cin>>S;
    stringstream ss(S);
    vector<string> v;
    while(getline(ss, s, ','))
        v.push_back(s);
    int l=0, r=v.size()-1, k=1;
    while(l<=r){
        if(l==r){
            cout<<v[l++]<<endl;
            break;
        }else
            cout<<v[l++]<<',';
        if(l==r){
            cout<<v[r--]<<endl;
            break;
        }else 
            cout<<v[r--]<<',';
    }
    return 0;
}

发表于 2019-10-16 00:42:00 回复(0)
直接把链表遍历一遍丢数组里去,然后头++,尾--重新连接就行
发表于 2023-06-05 22:35:19 回复(0)
package main

import (
    "fmt"
    "strings"
    "os"
    "bufio"
)

var in=bufio.NewReader(os.Stdin)

func main() {
    var s string
    fmt.Fscan(in,&s)
    arr:=strings.Split(s,",")
    if len(arr)==1{
        fmt.Print(arr[0])
        return
    }
    i,j:=0,len(arr)-1
    for i<j{
        if i==0{
            fmt.Printf("%v,%v",arr[i],arr[j])
        }else{
            fmt.Printf(",%v,%v",arr[i],arr[j])
        }
        i++
        j--
    }
    if i==j{
        fmt.Printf(",%v",arr[i])
    }
}

发表于 2023-03-22 13:58:46 回复(0)
694ms 35300KB Java

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    class ListNode {
        int value;
        ListNode next;

        ListNode(int i) {
            this.value = i;
        }
    }

    /**
     * 1. 根据输入生成链表
     * 2. 反转生成一个新链表
     * 3. 交叉取原链表和新链表的节点,取前n个
     */
    public static void main(String[] args) {
        new Main().print();
    }

    private void print() {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String[] chars = s.split(",");
        int[] arr = new int[chars.length];
        // 根据输入生成数组
        for (int i = 0; i < chars.length; i++) {
            arr[i] = Integer.parseInt(chars[i]);
        }

        int num = arr.length;
        if (num == 0) {
            return;
        }
        // 根据数组生成链表
        ListNode head = listfy(arr, num);
        ListNode result = revertn(head, num);
        for (int i = 0; i < num; i++) {
            if (i == num - 1) {
                System.out.print(result.value);
            } else {
                System.out.print(result.value + ",");
            }
            result = result.next;
        }
    }

    private ListNode listfy(int[] arr, int num) {
        ListNode virtualHead = new ListNode(0);
        ListNode temp = new ListNode(arr[0]);
        virtualHead.next = temp;
        for (int i = 1; i < num; i++) {
            temp.next = new ListNode(arr[i]);
            temp = temp.next;
        }
        return virtualHead.next;
    }

    private ListNode revertn(ListNode head, int num) {
        // 新生成一个反转链表(注意需要新生成链表而不是修改原来的链表)
        ListNode revertHead = revert(head);
        return merge(head, revertHead, num);
    }

    private ListNode revert(ListNode head) {
        ListNode temp = head;
        ListNode revertHead = new ListNode(0);
        ListNode newNode = null;
        while (temp != null) {
            newNode = new ListNode(temp.value);
            newNode.next = revertHead.next;
            revertHead.next = newNode;
            temp = temp.next;
        }
        return revertHead.next;
    }

    private ListNode merge(ListNode head, ListNode revertHead, int num) {
        if (num == 0) {
            return null;
        }
        ListNode temp = head.next;
        head.next = merge(revertHead, temp, --num);
        return head;
    }
}


发表于 2023-02-12 13:41:14 回复(0)
// 递归的爆栈的做法

const readline = require("readline")

const r1 = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})

const LinkNode = function (val) {
    this.val = val 
    this.next = null
}

const arrToLinkList = function(arr) {
    let dummyNode = new LinkNode(0)
    
    let prevNode = dummyNode
    
    for(let i = 0; i < arr.length; i++) {
        
        const curNode = new LinkNode(arr[i])
        
        // 连接节点
        prevNode.next = curNode
        
        prevNode = curNode
    }
    
    return dummyNode.next
}


const reverseLinkList = function (head) {
    let prevNode = head;
    
    const recurse = function (curNode) {
     
        if(!curNode) return false
        
        if(recurse(curNode.next)) return true
        
        // 提前结束recurse这个函数的条件是什么?
        if(prevNode === curNode) {
            // 断开prevNode和其下面的联系
            prevNode.next = null
            return true
        }
        
 
        // 切断当前节点和下一个节点的联系
        curNode.next = null
        
        // 建立新的联系前,先保存prevNode的下一个节点
        let temp = prevNode.next
        
        // 建立新的联系
        prevNode.next = curNode
        
        // 当前节点和prevNode的下一个节点连接起来
        curNode.next = temp
        
        // 更新prevNode的值
        prevNode = temp
        
        return false
    }
    
    recurse(prevNode)
}

r1.on("line", function (line) {
    const lineData = line.split(",")
    
    //将数组转化为链表
    let  head = arrToLinkList(lineData)
    
    // 进行反转链表的操作
    reverseLinkList(head)
    
    // 遍历链表
//     while(head) {
//         console.log(head.val)
        
//         head = head.next
//     }
  
    let strArr = []
    while(head) {
        strArr.push(head.val)
        
        head = head.next
    }
    
    // 我现在会输入读取,但是,如何按照它的结果输出呢?
    console.log(strArr.join(","))
    

})

发表于 2022-05-13 17:09:21 回复(0)

练习链表输入输出

import java.util.*;
import java.io.*;
public class Main{

    static class ListNode{
        int val;
        ListNode next;
        public ListNode(int val){
            this.val = val;
        }
    }

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        String[] s = str.split(",");
        ListNode head = new ListNode(0);
        ListNode tail = head;
        for(String _s : s){
            ListNode newNode = new ListNode(Integer.parseInt(_s));
            tail.next = newNode;
            tail = newNode;
        }
        reorderList(head.next);
        head = head.next;

        while(head != null){
            if(head.next == null) System.out.print(head.val);
            else System.out.print(head.val + ",");
            head = head.next;
        }

    }
    //找到链表中点,反转链表,合并两个链表
    public static void reorderList(ListNode head){
        if(head == null || head.next == null) return;
        ListNode mid = getMid(head);
        ListNode l2 = mid.next;
        l2 = reverseList(l2);
        mid.next = null;
        merge(head, l2);
    }

    //找到链表中点
    public static ListNode getMid(ListNode node){
        ListNode s = node, f = node;
        while(f != null && f.next != null){
            s = s.next;
            f = f.next.next;
        }
        return s;
    }

    //反转链表
    public static ListNode reverseList(ListNode node){
        ListNode pre = null;
        ListNode cur = node;
        while(cur != null){
            ListNode ne = cur.next;
            cur.next = pre;
            pre = cur;
            cur = ne;
        }
        return pre;
    }

    //合并连个链表
    public static void merge(ListNode l1, ListNode l2){
        ListNode p1 = l1, p2 = l2;
        while(l1 != null && l2 != null){
            p1 = l1.next; p2 = l2.next;
            l1.next = l2; l1 = p1;
            l2.next = l1; l2 = p2;
        }
    }
}
发表于 2022-02-26 16:59:56 回复(0)
inlude
发表于 2021-12-29 23:55:52 回复(0)

热门推荐

通过挑战的用户

查看代码