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

对于一个链表 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
正经的链表做法会被当成傻子吗?
#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 回复(2)
#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)
var line=readline();
var arr=line.split(',');
function a(arr){
    var i=0;
    var j=arr.length-1;
    var arr2=[];
    while(i<j){
        arr2.push(arr[i],arr[j]);
        i++;
        j--;
    
    }
    if(i==j){
        arr2.push(arr[i]);
        return arr2.join();
    }else{
        return arr2.join();
    }
}
print(a(arr)); 

发表于 2019-08-21 15:16:06 回复(0)
#include<bits/stdc++.h>
using namespace std;
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

int main() {
	
	int n;
	ListNode* head = new ListNode(0);
	ListNode* tmp = head;
	vector<int> arr;
	
	int inter;
	char ch;
	string s;
	getline(cin, s);
	istringstream is(s);
	while (is >> inter)
	{
		tmp->next = new ListNode(inter);
		tmp = tmp->next;
		is >> ch;
	}	
	if (head->next == nullptr) {
		cout << "error";
		return 0;
	}
	ListNode* fast = head->next;
	ListNode* slow = head->next;
	while (fast->next && fast->next->next) {
		fast = fast->next->next;
		slow = slow->next;
	}
	ListNode* cur = slow->next;
	ListNode* pre = NULL;
	slow->next = NULL;
	
	while (cur) {
		ListNode* lat = cur->next;
		cur->next = pre;
		pre = cur;
		cur = lat;	

	}
	cur = head->next;
	while (pre) {
		ListNode* p1 = pre->next;
		ListNode* l1 = cur->next;
		cur->next = pre;
		cur = l1;
		pre->next = cur;
		pre = p1;

	}

	while (head->next) {
		cout << head->next->val;
		head = head->next;
		if (head->next) {
			cout << ",";
		}
	}
	
	return 0;
}

发表于 2019-08-19 08:56:54 回复(0)
C++抄的左神
/*
利用stringstream进行字符串分割
将字符放在数组中一左一右的打印
最后的判断条件是left==right
*/
#include<iostream>
#include<vector>
#include<sstream>
#include<string>
using namespace std;
int main()
{
    string k; cin >> k;
    stringstream stream(k);
    vector<string> str;
    string tem;
    while(getline(stream,tem,',')) str.push_back(tem);
    int left  =0; int right = str.size()-1;
    bool rec = false;
    while( left <= right)
    {
        if(rec == false) 
        {
            if(left == right) cout << str[left++];
            else cout << str[left++] << ",";
            rec= true;
        }
        else{
            if(left == right) cout << str[right--];
            else cout << str[right--] << ",";
            rec = false;
        }
    }
    return 0;
}


发表于 2019-08-07 10:58:25 回复(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])


编辑于 2019-07-31 13:33:14 回复(0)
#include<iostream>
#include<deque>
#include<string>
using namespace std;

int main()
{
    string str;
    while(cin >> str)
    {
        int temp = 0;
        deque<int> deq;
        for(int i=0;i < str.size();i++)
        {
            if(str[i]!=',' && str[i] != '-')
                temp = temp * 10 + str[i] - '0';
            if(str[i] == ',')
            {
                deq.push_back(temp);
                temp = 0;
            }
        }
        deq.push_back(temp);
        while(!deq.empty())
        {
            cout << deq.front();
            deq.pop_front();
            if(!deq.empty())
                cout << ',';
            if(!deq.empty())
            {
                cout << deq.back();
                deq.pop_back();
                if(!deq.empty())
                    cout << ',';
            }
        }
        cout << endl;
    }
} 
1.提取字符串中的数字并压入deque中
2.deque双向打印、pop操作
发表于 2019-07-18 23:15:30 回复(0)
看了一下别人的解答都是数组做的。
贴一种效率极低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 回复(5)

热门推荐

通过挑战的用户

查看代码