实现反转单向链表和双向链表的函数。
如 1->2->3 反转后变成 3->2->1。
第一行一个整数 n,表示单链表的长度。
第二行 n 个整数 val 表示单链表的各个节点。
第三行一个整数 m,表示双链表的长度。
第四行 m 个整数 val 表示双链表的各个节点。
在给定的函数内返回相应链表的头指针。
3 1 2 3 4 1 2 3 4
3 2 1 4 3 2 1
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]))
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; }
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; }
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)); } }
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; }
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;
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; }
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;
}
#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; }
/* 仅实现单链表反转 */ #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; }
# 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; }
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(' '))
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; }反转单双链表,要背下来这个题目。
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; } }
# 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; }
主要时间都花在构建链表上了,真正逻辑的也没有几行。。。
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; } }