首页 > 试题广场 >

链表反转

[编程题]链表反转
  • 热度指数：538 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
链表反转： 1->2->3->4->5 通过反转后成为5->4->3->2->1。说明算法的复杂度。

输入描述:
第一行一个正整数n(1<=n<=100000)

第二行n个正整数a1,a2,...,an(1 <= ai <=100000)，表示链表顺序的结点值。


输出描述:
输出一行，n个数，表示反转后链表依次的结点值。
示例1

输入

10
9 10 6 6 8 7 5 7 7 5

输出

5 7 7 5 7 8 6 6 10 9
算法知识视频讲解
添加回答
封装成帧头像 封装成帧
三个指针, 分别指 当前节点, 前面的节点, 后面的节点 
public static ListNode reverse(ListNode root) {
    if (root == null)
        return null;
    ListNode pre = null;
    ListNode curr = root;
    ListNode next;
    while (curr != null) {
        next = curr.next;
        curr.next = pre;
        pre = curr;
        curr = next;
    }
    return pre;
}


发表于 2019-12-07 23:00:11 回复(0)
归来仍是少年v头像 归来仍是少年v 
import sys
if __name__ == '__main__':
    n = int(input())
    res = sys.stdin.readline().split()
    print(' '.join(res[::-1]))

发表于 2019-09-03 11:12:57 回复(1)
光辉岁月v头像 光辉岁月v 
#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;
	}

}

发表于 2020-08-03 11:09:18 回复(0)
牛客492718852号头像 牛客492718852号
# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>

typedef struct Node{
    int val;
    struct Node * pNext;
}NODE, *PNODE;

PNODE CreateLink();
PNODE ReverseLink(PNODE pHead);
void TraverseLink(PNODE p);

int main(void)
{
    PNODE pHead = CreateLink();
    pHead = ReverseLink(pHead);
    TraverseLink(pHead);
    return 0;
}

void TraverseLink(PNODE pHead)
{
    PNODE p = pHead;
    if (NULL == p)
        return;
    while (p != NULL)
    {
        printf("%d ", p->val);
        p = p->pNext;
    }
    printf("\n");
    return;
}

//单向链表的反转
PNODE ReverseLink(PNODE pHead)
{
    PNODE p = pHead;  // pHead不变
    PNODE q = pHead->pNext;
    PNODE t = p->pNext;

    if (p == NULL || p->pNext == NULL) //只存在一个元素  不需要进行反转
        return p;
    while (NULL != q->pNext)
        q = q->pNext;
    while (p != q)
    {
        p->pNext = q->pNext;
        q->pNext = p;
        p = t;
        t = t->pNext;
    }
    //需要返回新的头指针
    return p;
}

PNODE CreateLink()
{
    int i;
    int n;
    PNODE pNew;
    PNODE p;
    PNODE pHead = (PNODE)malloc(sizeof(NODE));  //使用了头结点，方便操作, 记得释放
    if (NULL == pHead)
    {
        printf("Fail to allocate memory\n");
        exit(-1);
    }
    pHead->pNext = NULL;

    scanf("%d", &n);
    p = pHead;
    for (i = 0; i < n; i++)
    {
        pNew = (PNODE)malloc(sizeof(NODE));
        if (NULL == pNew)
        {
        printf("Fail to allocate memory\n");
        exit(-1);
        }
        scanf("%d", &pNew->val);
        pNew->pNext = NULL;
        p->pNext = pNew;
        p = pNew;
    }

//注意  小心会有一个字节的泄漏
    p = pHead->pNext;
    free(pHead);
    return p;
}
编辑于 2020-06-07 08:59:22 回复(0)
布偶猫真好看头像 布偶猫真好看 
#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;
}

编辑于 2020-05-04 14:55:31 回复(0)
小妹妹的超仔头像 小妹妹的超仔
#include <stdio.h>
#include <stdlib.h>
typedef struct LinkedList{
    int data;
    struct LinkedList *next;
}*LinkedList,Node;

LinkedList InitLinkedList()
{
    LinkedList L;
    L = (LinkedList*)malloc(sizeof(LinkedList));
    if(L == NULL)
        printf("false");
    L->next = NULL;
    return L;
}

void output(LinkedList L)//遍历
{
    Node *p;
    for (p = L->next; p != NULL; p = p->next)
    {
        printf("%d ", p->data);
    }
}
int main(int argc,char **argv)
{
    int len;
    int flag =0;
    LinkedList L;
    scanf("%d ",&len);
    L = InitLinkedList();

    for(int i=0;i<len;i++){
        int data;
        scanf("%d",&data);
        getchar();
        //头插法
        Node *p;
        p = (Node*)malloc(sizeof(Node));
        p->data = data;
        p->next = L->next;
        L->next = p;
    }
 
     output(L);
 return 0;
}
发表于 2019-11-27 16:43:00 回复(0)
Python
gapex头像 gapex

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='')
发表于 2019-11-26 15:34:46 回复(0)
realmejt头像 realmejt
#include <stdio.h>
#include <stdlib.h>
#define unsigned int  uint

//链表的声明
typedef struct list
{
 int data;//数据域
 struct list *next;//指针域
}LIST,*P_LIST;
//头结点的声明
typedef struct hnode
{
 LIST *head;
 LIST *tail;
 
 int len;
}HNODE,*P_HONDE;
//尾插法
void tail_insert(HNODE *t,int data)
{
 LIST *new;
 new = malloc(sizeof(LIST)); 
 new->data = data;
 new->next = NULL;
 
 //如果链表为空
 if(t->len <= 0)
 { 
  t->head = new;   
  t->tail = new;
  t->len = 1;  
  return ;  
 }
 
 t->tail->next = new;
 t->tail = new;
 t->len++;
}
//链表逆序
void reversal_list(HNODE *l)
{
 LIST *left,*right;
 
 left  = l->head;
 right = l->tail;
 
 while(left != right)
 {
  int tmp = 0;
  tmp = left->data;
  left->data = right->data;
  right->data = tmp;
  
  left++;
  right--;
 }
}
//链表输出
void pri_list(HNODE *t)
{
 LIST *new;
 new = t->head;
 
 if(t->len <= 0)
 {
  printf("链表为空！\n");
 }
 while(new)
 {
  printf("%d",new->data);
  new = new->next;
 }
 printf("\n");
}
int main(int argc,char **argv)
{
 HNODE *t;
 t= malloc(sizeof(HNODE));
 
 t->head = NULL;
 t->tail = NULL;
 t->len = 0;
 
 int len; //输入节点数
 int i;
 
 printf("请输入节点总值\n");
 scanf("%d ",&len);
 
 for(i = 0; i < len; i++)
 {
  int data;
  scanf("%d",&data);
  getchar();
  tail_insert(t,data);
 }
 pri_list(t);//输出原链表
 
 reversal_list(t);
 pri_list(t);//输出逆序后的链表
 
 return 0;
}
发表于 2019-09-10 13:44:38 回复(1)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 c#工程师 数据库工程师 瓜子二手车 2019 大数据开发工程师 Java工程师
上传者：小小
难度：
8条回答 3521浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号