第一行一个正整数n(1<=n<=100000)
第二行n个正整数a1,a2,...,an(1 <= ai <=100000),表示链表顺序的结点值。
输出一行,n个数,表示反转后链表依次的结点值。
10 9 10 6 6 8 7 5 7 7 5
5 7 7 5 7 8 6 6 10 9
#include<iostream> using namespace std; struct ListNode { int val; ListNode *next; }; int main(){ int n; cin>>n; int i; struct ListNode*head = NULL; struct ListNode*p,*q; for(i=0;i<n;i++){ p = new ListNode; cin>>p->val; p->next = NULL; if(head == NULL){ head = p; q = p; }else{ q->next = p; q = p; } } struct ListNode*nhead = NULL; q = head; while (q) { if (nhead == NULL) { nhead = q; q = q->next; nhead->next = NULL; } else { p = q; q = q->next; p->next = nhead; nhead = p; } } q = nhead; while (q) { cout<<q->val<<" "; q=q->next; } }
#include <iostream> #include <vector> using namespace std; struct ListNode { int val; ListNode *next; ListNode(int x): val(x), next(NULL){} }; class Solution { public: ListNode* reveseListNode(ListNode* head) { ListNode *pre = head; ListNode *cur = NULL; ListNode *temp = NULL; while(pre) { temp = pre->next; pre->next = cur; cur = pre; pre = temp; } return cur; } }; ListNode* build(vector<int>& res, int begin, int end) { if(begin >= end) return NULL; ListNode *node = new ListNode(res[begin]); node->next = build(res, begin + 1, end); return node; } int main() { int n; cin >> n; vector<int> res; while(n--) { int temp; cin >> temp; res.push_back(temp); } int len = res.size(); ListNode *head = build(res, 0, len); Solution solution; ListNode *ans = solution.reveseListNode(head); while(ans->next) { cout << ans->val << ' '; ans = ans->next; } cout << ans->val; return 0; }
Python3,n没用
class Node: def __init__(self, val, next=None): self.val = val self.next = next n = int(input()) nums = input().split() head = Node('head') tail = head for num in nums: node = Node(num) tail.next = node tail = node def inverse(head: Node) -> Node: '''给定链表第一个有效节点,反转单链表''' if head is None or head.next is None: return prev, curr, next = None, head, None while curr is not None: next = curr.next curr.next = prev prev = curr curr = next return prev tail = head.next head.next = inverse(head.next) node = head.next while node is not tail: print(node.val, end=' ') node = node.next else: assert tail.val == node.val print(tail.val, end='')