翻转链表

#整体思路是：
#先根据输入初始化成一个单链表
#然后复制一个刚生成的链表
#把其中一个链表进行反转
#按照链表长度的一半次数合并两个链表，即可生成题目要求的链表
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()

//先用快慢指针拆分链表，翻转后半部分，再和前半部分拼接；
#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;
}

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

}

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

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])

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

}

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

    }

}

#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(',');
  }
}

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

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

练习链表输入输出

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