反转单向链表_

pein531

分别写出两种链表的反转方法

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

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

class ListDNode {
    int val;
    ListDNode prev;
    ListDNode next;
    public ListDNode(int val) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] list1 = br.readLine().trim().split(" ");
        int m = Integer.parseInt(br.readLine().trim());
        String[] list2 = br.readLine().trim().split(" ");
        ListNode head1 = new ListNode(Integer.parseInt(list1[0]));
        ListDNode head2 = new ListDNode(Integer.parseInt(list2[0]));
        ListNode cur1 = head1;
        ListDNode cur2 = head2;
        for(int i = 1; i < list1.length; i++){
            cur1.next = new ListNode(Integer.parseInt(list1[i]));
            cur1 = cur1.next;
        }
        for(int i = 1; i < list2.length; i++){
            cur2.next = new ListDNode(Integer.parseInt(list2[i]));
            ListDNode prev = cur2;
            cur2 = cur2.next;
            cur2.prev = prev;
        }
        ListNode result1 = reverseList(head1);
        ListDNode result2 = reverseDList(head2);
        while(result1 != null){
            System.out.print(result1.val + " ");
            result1 = result1.next;
        }
        System.out.println();
        while(result2 != null){
            System.out.print(result2.val + " ");
            result2 = result2.next;
        }
    }
    
    // 反转单向链表
    private static ListNode reverseList(ListNode cur) {
        ListNode prev = null;
        while(cur != null){
            ListNode temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
    
    // 反转双向链表
    private static ListDNode reverseDList(ListDNode head) {
        ListDNode prev = head;
        ListDNode cur = head.next;
        head.next = null;
        while(cur != null){
            ListDNode temp = cur.next;
            cur.next = prev;
            prev.prev = cur;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
}

这种题目需要自己构建链表，而不是实现一个输入为链表，输出也为链表的函数，作为机考题只需要打印的话还是可以作弊的，毕竟只需要打印就没人知道你这个打印结果是不是通过算法得来的。为了快速AC然后去做其他题目，不妨考虑一下流氓做法。

n = int(input())
list1 = input().strip().split()
m = int(input())
list2 = input().strip().split()
print(' '.join(list1[::-1]))
print(' '.join(list2[::-1]))

编辑于 2021-06-02 09:26:09 回复(0)

C/C++

三十不惑mm

list_node * reverse_list(list_node * head)
{
//////在下面完成代码
list_node* pPrenode =nullptr;
list_node* pCurrnode = head;
while(pCurrnode->next!=nullptr){
list_node* pNextnode = pCurrnode->next;
pCurrnode->next = pPrenode;
pPrenode = pCurrnode;
pCurrnode = pNextnode;
}
pCurrnode->next = pPrenode;
return pCurrnode;

}

double_list_node * reverse_double_list(double_list_node * head)
{
//////在下面完成代码
double_list_node* pPrenode = nullptr;
double_list_node* pCurrnode = head;
//double_list_node* pNextNode = pCurrnode->next;
while(pCurrnode->next!=nullptr){
double_list_node* ptmp = pCurrnode->next;
pCurrnode->next = pCurrnode->pre;
pCurrnode->pre = ptmp;
pPrenode = pCurrnode;
pCurrnode = ptmp;
}
pCurrnode->next = pPrenode;
return pCurrnode;

}

发表于 2020-07-23 19:24:53 回复(0)

offer之神降临吧

list_node * reverse_list(list_node * head)
{
    //////在下面完成代码
    // 头插法
    /***
    list_node * dummy = new list_node();
    dummy->next = nullptr;

    list_node * cur = head;
    list_node * temp;
    while(cur){
        temp = cur;
        cur = cur->next;
        temp->next = dummy->next;
        dummy->next = temp;
    }
    return dummy->next;
    ***/
    //三指针法
    list_node * q, *cur, *p;
    q = nullptr;
    cur = head;
    p = head;
    while(cur){
        p = p->next;
        cur->next = q;
        q = cur;
        cur = p;
    }
    return q;
}

double_list_node * reverse_double_list(double_list_node * head)
{
    //////在下面完成代码
    double_list_node * q, *cur, *p;
    q = nullptr;
    cur = head;
    p = head;
    
    while(cur){
        p = p->next;
        cur->next = q;
        cur->pre = p;
        q = cur;
        cur = p;
    }
    return q;
}

发表于 2020-05-10 13:10:50 回复(0)

C/C++

nbgao

list_node * reverse_list(list_node * head)
{
    list_node *pre=NULL, *cur=head, *p;
    while(cur){
        p = cur->next;
        cur->next = pre;
        pre = cur;
        cur = p;
    }
    return pre;
}

double_list_node * reverse_double_list(double_list_node * head)
{
    double_list_node *pre=NULL, *cur=head, *p;
    while(cur){
        p = cur->next;
        cur->next = pre;
        cur->pre = p;
        pre = cur;
        cur = p;
    }
    return pre;
}

编辑于 2020-04-28 00:57:55 回复(0)

Java

void12

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Scanner;
public class Main{
    public static class ListNode{
        int var;
        ListNode next;
        ListNode(int var){
            this.var = var;
        }
    }
    public static class DListNode{
        int var;
        DListNode next;
        DListNode prev;

        DListNode(int var){
            this.var = var;
        }
    }


    public static ListNode createListNode(int N, String[] strs){
        //ListNode head = new ListNode(0);  //don't init it as 0, we'd better use first value of the array to initialize head
        ListNode head = new ListNode(Integer.valueOf(strs[0]));
        ListNode tail = head;
        for(int i=1;i<N;i++){
            ListNode newNode = new ListNode(Integer.valueOf(strs[i]));
            tail.next = newNode;
            tail = tail.next;
        }
        return head;
    }

    public static DListNode createDListNode(int N, String[] strs){
        DListNode dListHead = new DListNode(Integer.valueOf(strs[0]));
        DListNode curDListNode = dListHead;
        for(int i=1;i<N;i++){
            DListNode newDListNode = new DListNode(Integer.valueOf(strs[i]));
            curDListNode.next = newDListNode;
            newDListNode.prev = curDListNode;
            curDListNode = curDListNode.next;
        }
        return dListHead;
    }

    public static ListNode reverseList(ListNode head){
        ListNode prev = null;
        ListNode next;
        ListNode cur = head;
        while(cur != null){
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    public static DListNode reverseDList(DListNode head){
        DListNode prev = null;
        DListNode next;
        DListNode cur = head;
        while(cur != null){
            next = cur.next;
            cur.next = prev;
            cur.prev = next;

            prev = cur;
            cur = next;
        }
        return prev;
    }

    public static void show(ListNode head){
        while(head!=null){
            System.out.print(head.var + " ");
            head = head.next;
        }
        System.out.println();
    }
    public static void show(DListNode head){
        while(head!=null){
            System.out.print(head.var + " ");
            head = head.next;
        }
        System.out.println();
    }
    public static void main(String[] argv) throws FileNotFoundException {
        Scanner sc = new Scanner(System.in);
        //Scanner sc = new Scanner(new BufferedReader(new FileReader("src/ReverseListInput.txt")));
        String strFirstLine = sc.nextLine();
        int N = Integer.valueOf(strFirstLine);
        String strSecondLine = sc.nextLine();
        String strSecondLineArray[] = strSecondLine.split(" ");
        ListNode listNodeHead = createListNode(N,strSecondLineArray);

        String strThirdLine = sc.nextLine();
        int M = Integer.valueOf(strThirdLine);
        String strFourthLine = sc.nextLine();
        String strFourthLineArray[] = strFourthLine.split(" ");

        show(reverseList(listNodeHead));

        DListNode dListHead = createDListNode(M,strFourthLineArray);
        show(reverseDList(dListHead));
    }
}

发表于 2019-12-08 15:12:26 回复(0)

Spectre_

list_node * reverse_list(list_node * head)
{
    //////在下面完成代码
    list_node* pre = NULL;
    list_node* cur = head;
    list_node* next;
    while (cur)
    {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

double_list_node * reverse_double_list(double_list_node * head)
{
    //////在下面完成代码
    double_list_node* pre = NULL;
    double_list_node* cur = head;
    double_list_node* next;
    while (cur)
    {
        next = cur->next;
        cur->next = pre;
        cur->pre = next;
        pre = cur;
        cur = next;
    }
    return pre;
}

发表于 2019-10-13 20:48:39 回复(0)

C/C++

昔遥暮云

list_node * reverse_list(list_node * head)
{
    //////在下面完成代码
    list_node* newhead=nullptr,*cur=head,*next;
    while(cur){
        next=cur->next;
        cur->next=newhead;
        newhead=cur;
        cur=next;
    }
    return newhead;

}

double_list_node * reverse_double_list(double_list_node * head)
{
    //////在下面完成代码
    double_list_node* newhead=nullptr,*cur=head,*next;
    while(cur){
        next=cur->next;
        cur->next=newhead;
        newhead=cur;
        cur=next;
    }
    return newhead;

编辑于 2019-10-16 08:56:25 回复(0)

无心2019

list_node * reverse_list(list_node * head)
{
    //////在下面完成代码
    list_node *p=head;
    list_node *q=p->next;
    head->next=NULL;
    while(q)
    {
        list_node *r=q->next;
        q->next=p;
        p=q;
        q=r;
    }
    return p;
}

double_list_node * reverse_double_list(double_list_node * head)
{
    //////在下面完成代码
    double_list_node *p=head;
    double_list_node *q=p->next;
    head->next=NULL;
    while(q)
    {
        double_list_node *r=q->next;
        q->next=p;
        p->pre=q;
        p=q;
        q=r;
    }
    return p;
}

发表于 2019-09-15 22:33:55 回复(0)

唉梅子



	list_node * reverse_list(list_node * head)
{
    //////在下面完成代码
    list_node *pre = nullptr;
    list_node *cur = head;
    list_node *next = nullptr;
    list_node *node = nullptr;
    while(cur){
        next = cur->next;
        if(next == nullptr)
            node = cur;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return node;
}



	double_list_node * reverse_double_list(double_list_node * head)
{
    //////在下面完成代码
    double_list_node *pre = nullptr;
    double_list_node *cur = head;
    double_list_node *next = nullptr;
    double_list_node *node = nullptr;
    while(cur){
        next = cur->next;
        if(next == nullptr)
            node = cur;
        cur->next = pre;
        cur->pre = next;//多一步
        pre = cur;
        cur = next;
    }
    return node;
}

发表于 2019-08-02 19:48:42 回复(0)

阿金要努力

#include<iostream>
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(nullptr) {}
};

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

ListNode* reverseList(ListNode* head) {
    ListNode* tail = head, * prev = nullptr;
    while (tail) {
        ListNode* nextNode = tail->next;
        tail->next = prev;
        prev = tail;
        tail = nextNode;
    }
    return prev;
}

DoubListNode* reverseDoublList(DoubListNode* head) {
    DoubListNode* tail = head, * prev = nullptr;
    while (tail) {
        DoubListNode* nextNode = tail->next;
        tail->next = prev;
        tail->prev = nextNode;
        prev = tail;
        tail = nextNode;
    }
    return prev;
}

template<typename T>
void printList(T* head) {
    T* cur = head;
    while (cur) {
        std::cout << cur->val << " ";
        cur = cur->next;
    }
    std::cout << std::endl;
}

int main() {
    int n, num1;
    std::cin >> n;
    ListNode* head1 = nullptr;
    ListNode* tail1 = nullptr;
    for (int i = 0; i < n; i++) {
        std::cin >> num1;
        ListNode* newNode1 = new ListNode(num1);
        if (head1 == nullptr) {
            head1 = newNode1;
            tail1 = newNode1;
        } else {
            tail1->next = newNode1;
            tail1 = newNode1;
        }
    }
    int m, num2;
    std::cin >> m;
    DoubListNode* head2 = nullptr;
    DoubListNode* tail2 = nullptr;
    for (int i = 0; i < m; i++) {
        std::cin >> num2;
        DoubListNode* newNode2 = new DoubListNode(num2);
        if (head2 == nullptr) {
            head2 = newNode2;
            tail2 = newNode2;
        } else {
            tail2->next = newNode2;
            newNode2->prev = tail2;
            tail2 = newNode2;
        }
    }
    ListNode* newHead = reverseList(head1);
    printList(newHead);

    DoubListNode* newHead2 = reverseDoublList(head2);
    printList(newHead2);

    return 0;
}

发表于 2023-07-03 21:41:56 回复(0)

C/C++

拉普拉斯不拉丝

//用了两次单向链表的反转实现双向链表的反转

//单向链表的反转

list_node* pre=nullptr;
    list_node* cur=head;
    list_node* tmp=new list_node();
    while(cur!=NULL){
        tmp=cur->next;
        cur->next=pre;
        pre=cur;
        cur=tmp;
    }
    return pre;

使用了一个pre，一个tmp，使用cur遍历链表。算是一个窗？

编辑于 2022-05-06 21:29:25 回复(0)

C

helloxuanbao

/* 仅实现单链表反转 */
#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int val;
    struct node *next;
} Node;

Node *newNode(int val);

void freeList(Node *head);

void printList(Node *head);

Node *createList(int n);

Node *reverseList(Node *head);

int main(void) {
    int n;
    Node *head = NULL;
    scanf("%d", &n);
    head = createList(n);
    head = reverseList(head);
    printList(head);
    freeList(head);
    scanf("%d", &n);
    head = createList(n);
    head = reverseList(head);
    printList(head);
    freeList(head);
    return 0;
}

Node *newNode(int val) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->val = val;
    node->next = NULL;
    return node;
}

void freeList(Node *head) {
    Node *old;
    while (head != NULL) {
        old = head;
        head = head->next;
        free(old);
    }
}

void printList(Node *head) {
    Node *cur = head;
    while (cur != NULL) {
        printf("%d", cur->val);
        cur = cur->next;
        if (cur != NULL)
            printf(" ");
    }
    printf("\n");
}

Node *createList(int n) {
    Node *head = NULL, *cur = NULL, *node;
    int val;
    for (int i = 0; i < n; i++) {
        scanf("%d", &val);
        node = newNode(val);
        if (head == NULL) {
            head = node;
            cur = node;
            continue;
        }
        cur->next = node;
        cur = cur->next;
    }
    return head;
}

Node *reverseList(Node *head) {
    Node *next, *pre = NULL;
    while (head != NULL) {
        next = head->next;
        head->next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

发表于 2022-02-06 23:18:54 回复(0)

Python 3

毓毓子最可爱

n = int(input())
linkList1 = input().split(' ')
print(' '.join(linkList1[::-1]))
m = int(input())
linkList2 = input().split(' ')
print(' '.join(linkList2[::-1]))

发表于 2021-09-07 09:10:41 回复(0)

C++

牛客66319561号

C++,双百分之百。

# include <bits/stdc++.h>
using namespace std;

struct list_node{
    int val;
    struct list_node * next;
};
struct double_list_node{
    int val;
    struct double_list_node * pre, * next;
};

list_node * input_list(void)
{
    int n, val;
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else {
            list_node * new_pnode = new list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}

double_list_node * input_double_list(void)
{
    int n, val;
    double_list_node * phead = new double_list_node();
    double_list_node * cur_pnode = phead;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
            cur_pnode->pre = NULL;
        }
        else {
            double_list_node * new_pnode = new double_list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            new_pnode->pre = cur_pnode;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}

list_node * reverse_list(list_node * head)
{
    //////在下面完成代码
    list_node* pre=head,*cur=head->next;
    list_node* tmp=NULL;
    pre->next=NULL;
    while(cur!=NULL){
        tmp=cur;
        cur=cur->next;
        tmp->next=pre;
        pre=tmp;
    }
    return pre;
}

double_list_node * reverse_double_list(double_list_node * head)
{
    //////在下面完成代码
    double_list_node* pre=head,*cur=head->next,*tmp=NULL;
    pre->next=NULL;
    while(cur!=NULL){
        tmp=cur;
        cur=cur->next;
        tmp->next=pre;
        pre->pre=tmp;
        pre=tmp;
    }
    return pre;
}

void print_list(list_node * head)
{
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}

void print_double_list(double_list_node * head)
{
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}

int main ()
{
    list_node * head = input_list();
    double_list_node * double_head = input_double_list();
    list_node * new_head = reverse_list(head);
    double_list_node * new_double_head = reverse_double_list(double_head);
    print_list(new_head);
    print_double_list(new_double_head);
    return 0;
}

发表于 2021-07-27 10:03:42 回复(0)

Relili

不想吃

let n=parseInt(readline()) 
let list=readline().split(' ').map(item=>parseInt(item))
let m=parseInt(readline()) 
let doublelist=readline().split(' ').map(item=>parseInt(item))
const listNode=function(val){
    this.val=val;
    this.next=null
}
const doublelistNode=function(val){
    this.val=val;
    this.pre=null
    this.next=null
}
const head=new listNode(-1)
const doublehead=new doublelistNode(-1)
let p=head
for(let i=0;i<n;i++){
    const node = new listNode(list[i])
    p.next=node
    p=node
}
 p=doublehead
for(let i=0;i<m;i++){
    const node = new doublelistNode(doublelist[i])
    p.next=node
    node.pre=p
    p=node
}

p=head.next
const headreverse=new listNode(-1)
while(p){
    head.next=p.next
    p.next= headreverse.next
   headreverse.next= p
   p=head.next
}

p=doublehead.next
const doubleheadreverse=new doublelistNode(-1)
while(p){
    if(p.next)p.next.pre=doublehead
    doublehead.next=p.next
    p.next=doubleheadreverse.next
    p.pre=doubleheadreverse
    if(p.next!=null){
        p.next.pre=p
    }
    doubleheadreverse.next=p 
    p=doublehead.next
}
p=headreverse.next
let res=[]
while(p){
    res.push(p.val)
    p=p.next
}
console.log(res.join(' '))

res=[]
p=doubleheadreverse.next
while(p){
    res.push(p.val)
    p=p.next
}
console.log(res.join(' '))

编辑于 2021-07-01 14:01:05 回复(0)

C/C++

珞喻东路小法师丶

list_node * reverse_list(list_node * head)
{
    //////在下面完成代码
    if (head == nullptr)
        return head;
    list_node* pre = nullptr;
    list_node* cur = head;
    list_node* next;
    while (cur != nullptr)
    {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

double_list_node * reverse_double_list(double_list_node * head)
{
    //////在下面完成代码
        //////在下面完成代码
    if (head == nullptr)
        return head;
    double_list_node* pre = nullptr;
    double_list_node* cur = head;
    double_list_node* next;
    while (cur != nullptr)
    {
        next = cur->next;
        cur->next = pre;
        cur->pre = next;
        pre = cur;
        cur = next;
    }
    return pre;
}

反转单双链表，要背下来这个题目。

发表于 2021-06-16 11:09:10 回复(0)

牛客887263087号

# include <bits/stdc++.h>
using namespace std;

struct list_node{
int val;
struct list_node * next;
};
struct double_list_node{
int val;
struct double_list_node * pre, * next;
};

list_node * input_list(void)
{
int n, val;
list_node * phead = new list_node();
list_node * cur_pnode = phead;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &val);
if (i == 1) {
cur_pnode->val = val;
cur_pnode->next = NULL;
}
else {
list_node * new_pnode = new list_node();
new_pnode->val = val;
new_pnode->next = NULL;
cur_pnode->next = new_pnode;
cur_pnode = new_pnode;
}
}
return phead;
}

double_list_node * input_double_list(void)
{
int n, val;
double_list_node * phead = new double_list_node();
double_list_node * cur_pnode = phead;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &val);
if (i == 1) {
cur_pnode->val = val;
cur_pnode->next = NULL;
cur_pnode->pre = NULL;
}
else {
double_list_node * new_pnode = new double_list_node();
new_pnode->val = val;
new_pnode->next = NULL;
new_pnode->pre = cur_pnode;
cur_pnode->next = new_pnode;
cur_pnode = new_pnode;
}
}
return phead;
}

list_node * reverse_list(list_node * head)
{
//////在下面完成代码
list_node *pre = nullptr;
list_node *cur = head;
list_node *next = nullptr;
while(cur != nullptr && cur->next != nullptr){
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
cur->next = pre;
return cur;
}

double_list_node * reverse_double_list(double_list_node * head)
{
//////在下面完成代码
double_list_node *pre = nullptr;
double_list_node *cur = head;
double_list_node *next = nullptr;
while(cur != nullptr && cur->next != nullptr){
next = cur->next;
cur->next = pre;
cur->pre = next;
pre = cur;
cur = next;
}
cur->next = pre;
cur->pre = nullptr;
return cur;
}

void print_list(list_node * head)
{
while (head != NULL) {
printf("%d ", head->val);
head = head->next;
}
puts("");
}

void print_double_list(double_list_node * head)
{
while (head != NULL) {
printf("%d ", head->val);
head = head->next;
}
puts("");
}

int main ()
{
list_node * head = input_list();
double_list_node * double_head = input_double_list();
list_node * new_head = reverse_list(head);
double_list_node * new_double_head = reverse_double_list(double_head);
print_list(new_head);
print_double_list(new_double_head);
return 0;

}

主要发生的错误是：

pre -> cur -> next 处理的是cur

发表于 2021-05-15 15:58:46 回复(0)

復活の検事

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Node node = new Node(scanner.nextInt());
        Node head1 = node;
        for(int i=1;i<n;i++) {
            Node next = new Node(scanner.nextInt());
            node.next = next;
            node = next;
        }
        int m = scanner.nextInt();
        DoubleNode doubleNode = new DoubleNode(scanner.nextInt());
        DoubleNode head2 = doubleNode;
        DoubleNode last = null;
        for(int i=1;i<m;i++) {
            DoubleNode next = new DoubleNode(scanner.nextInt());
            doubleNode.last = last;
            doubleNode.next = next;
            last = doubleNode;
            doubleNode = next;
        }
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        Node result1 = removeNode(head1);
        while(result1 != null) {
            sb1.append(result1.value).append(" ");
            result1 = result1.next;
        }
        DoubleNode result2 = removeDoubleNode(head2);
        while(result2 != null) {
            sb2.append(result2.value).append(" ");
            result2 = result2.next;
        }
        System.out.println(sb1.toString().trim());
        System.out.println(sb2.toString().trim());
    }
    
    public static Node removeNode(Node node) {
        if(node == null) {
            return node;
        }

        Node pre = null;
        Node next = null;
        while(node != null) {
            next = node.next;
            node.next = pre;
            pre = node;
            node = next;
        }
        
        return pre;
    }
    
    public static DoubleNode removeDoubleNode(DoubleNode node) {
        if(node == null) {
            return node;
        }

        DoubleNode pre = null;
        DoubleNode next = null;
        while(node != null) {
            next = node.next;
            node.next = pre;
            node.last = next;
            pre = node;
            node = next;
        }
        
        return pre;
    }
}

class Node {
    public int value;
    public Node next;
    
    public Node(int data) {
        this.value = data;
    }
}

class DoubleNode {
    public int value;
    public DoubleNode last;
    public DoubleNode next;
    
    public DoubleNode(int value) {
        this.value = value;
    }
}

发表于 2021-04-21 19:32:10 回复(0)

7777gloryglory

单链表的逆置使用三指针法。

同理双向链表也可以使用三指针法。

# include <bits/stdc++.h>
#include <stdio.h>

using namespace std;

struct list_node{
    int val;
    struct list_node * next;
};
struct double_list_node{
    int val;
    struct double_list_node * pre, * next;
};

list_node * input_list(void)
{
    int n, val;
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else {
            list_node * new_pnode = new list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}

double_list_node * input_double_list(void)
{
    int n, val;
    double_list_node * phead = new double_list_node();
    double_list_node * cur_pnode = phead;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
            cur_pnode->pre = NULL;
        }
        else {
            double_list_node * new_pnode = new double_list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            new_pnode->pre = cur_pnode;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}

list_node * reverse_list(list_node * head)
{
    //////在下面完成代码
    if(!head) {
        return nullptr;
    }
    
    list_node* prev = NULL;
    list_node* cur = head;
    list_node* next = NULL;
    
    while(cur) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

double_list_node * reverse_double_list(double_list_node * head)
{
    //////在下面完成代码

    if(!head) {
        return nullptr;
    }
    
    double_list_node* prev = NULL;
    double_list_node* cur = head;
    double_list_node* next = NULL;
    
    while(cur) {
        next = cur->next;
        
        cur->next = prev;
        if(next)
            cur->pre = next;
        
        prev = cur;
        cur = next;
    }
    return prev;

}

void print_list(list_node * head)
{
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}

void print_double_list(double_list_node * head)
{
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}

int main ()
{
    list_node * head = input_list();
    double_list_node * double_head = input_double_list();
    list_node * new_head = reverse_list(head);
    double_list_node * new_double_head = reverse_double_list(double_head);
    print_list(new_head);
    print_double_list(new_double_head);
    return 0;
}

发表于 2020-08-06 11:34:11 回复(0)

p_string

主要时间都花在构建链表上了，真正逻辑的也没有几行。。。

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int singleCnt = Integer.parseInt(br.readLine().trim());
        String[] rawInput = br.readLine().trim().split(" ");
        // 构建单链表
        Node singleHead = buildSingleLinkedList(rawInput);

        int doubleCnt = Integer.parseInt(br.readLine().trim());
        rawInput = br.readLine().trim().split(" ");
        // 构建双向链表
        Node doubleHead = buildDoubleLinkedList(rawInput);

        // 反转链表
        singleHead = reverseSingleList(singleHead);
        doubleHead = reverseDoubleList(doubleHead);

        // 打印链表
        printList(singleHead);
        printList(doubleHead);

        br.close();
    }

    private static Node buildSingleLinkedList(String[] rawInput) {
        Node head = null, curNode = null;
        for (int i = 0; i < rawInput.length; i++) {
            Node tmpNode = new Node(Integer.parseInt(rawInput[i]));
            if (null == head) {
                head = tmpNode;
            } else {
                curNode.next = tmpNode;
            }
            curNode = tmpNode;
        }
        return head;
    }

    private static Node buildDoubleLinkedList(String[] rawInput) {
        Node head = null, curNode = null, lastNode = null;

        for (int i = 0; i < rawInput.length; i++) {
            Node tmpNode = new Node(Integer.parseInt(rawInput[i]));
            if (null == head) {
                head = tmpNode;
            } else {
                curNode.next = tmpNode;
            }
            curNode = tmpNode;
            curNode.last = lastNode;
            lastNode = tmpNode;
        }

        return head;
    }

    // 反转单链表
    private static Node reverseSingleList(Node head) {
        if (null == head) {
            return head;
        }
        Node pre = null, curNode = head;
        while (null != curNode) {
            Node next = curNode.next;
            curNode.next = pre;
            pre = curNode;
            curNode = next;
        }
        head = pre;
        return head;
    }

    // 反转双链表
    private static Node reverseDoubleList(Node head) {
        if (null == head) {
            return head;
        }
        Node pre = null, curNode = head;
        while (null != curNode) {
            Node next = curNode.next;
            curNode.last = next;
            curNode.next = pre;
            pre = curNode;
            curNode = next;
        }
        head = pre;
        return head;
    }

    // 打印链表
    private static void printList(Node head) {
        StringBuilder sb = new StringBuilder();
        while (null != head) {
            sb . append(head.value) . append(" ");
            head = head.next;
        }
        System.out.println(sb.toString().trim());
    }
}
class Node {
    public int value;
    public Node next;
    public Node last;
    public Node(int value) {
        this.value = value;
        next = null;
        last = null;
    }
}

发表于 2020-07-20 00:03:33 回复(0)

反转单向链表

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题