链表反转（java链表反转）

本篇文章给大家谈谈链表反转，以及java链表反转对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、设计一个算法，利用单链表原来的结点空间将一个单链表就地逆转
• 2、单链表解题思维
• 3、K个一组反转链表
• 4、c++链表反转。有要求

设计一个算法，利用单链表原来的结点空间将一个单链表就地逆转

1.建立两个指针struct* p，q，p=head,q=p-next,即最开始山毕p指向链表的第1项，q指向第2项

2.if q-next !=NULL, p=p-next,q=q-next

3.endif q-物唯汪next ==NULL,即q指向最后一项，p指向倒罩仔数第二项

新建一个指针，保存原表尾的地址 struct*t=q

4.q-next=p,q=p //倒数第一项指向倒数第二项，将q指向倒数第二项

5.p=head //p重新重表头开始遍历

6.if p-next !=q,p=p-next //如果p指向的不是q指向的前一项，则p继续向后遍历

7.endif p-next ==q //q指向p的前一项

8. q-next =p,q=p //重复第4步

9.p=head //重复第5步。

。。。

。。。

N. until q=p=head

至此，原链表已经完全逆转，然后让头指针指向原链表的表尾，即指向新链表的表头 head=t，这样就搞定了

----------------------------------------------------------

马上要停电了，没时间检查，上面是我粗略的想法，应该有很好的改进方案，先关机，免得电脑被闪了

[img]

单链表解题思维

一、概念

链表兄宽由一组零散的结点通掘庆过指针连接而成，每个结点都包含当前结点内容和后继指针。相对于数组，它不受固于存储空间的限制，可更快捷地进行插入和删除操作，主要有以下几种类型：

1、单链表

指针指向下一个节点，终点指向 null

2、双链表

指针指向前一个节点和后一个节点

3、循环链表

最后一个节点指向第一个节点

在解决链表相关问题时，先执行三步骤，再敲下代码会更清晰

不同于数组，JS官方还没有提供一个直接的链表API，可通过对象的方式模拟出链表，其结构为

二、leetcode 最常见相关题型

1、 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

步骤：

2、 环形链表

给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。如果链表中存在环，返回 true 否则返回 false 。要求用 O(1) 内存解决此问题

pos 表示链表尾连接到链表中的位置，若 pos 是 -1 则该链表中没有环

步骤：

3、 反转链表

给你单链表的头节点 head ，请你使用迭代或递归地反转链表，并返回反转后羡散亮的链表

步骤：

4、 链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点，如果有两个中间结点，则返回第二个中间结点（给定链表的结点数介于 1 和 100 之间）

步骤：

5、 删除链表倒数第 n 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点

步骤：

6、 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false

步骤：

8、 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。题目数据保证整个链式结构中不存在环。

注意：

步骤：

9、 链表求和

给定两个用链表表示的整数，每个节点包含一个数位，这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果

步骤：

K个一组反转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正答搏轮整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1-2-3-4-5

当 k = 2 时，应当返回: 2-1-4-3-5

当 k = 3 时，应当返回: 3-2-1-4-5

链接：

本题思路并不难得出，只是在实现上需要注意的细节较多。设置一个计数器n，以及p1,p2划分出当前区间，当n是k的倍数时反转该区间的链表（特别地，当n==k时将ans置为当前节点），设置一个temp为已排序链表的尾部，初始时为空,每次反转之前先将p2接在temp后，设置一个ne节点存储p2的下一个节点，然后反转区间内银笑链表，将temp移到p1，将p1与p2都移动到ne。

当跳出循环时，若有剩余节点未反转（即n%k!=0）,此时p1位于剩余节点头部，其尾部未反转处于置空状态，将p1接到p2之后并返回ans即可，若无剩余节点未反转，因为每次反转过程清信中都会将尾部置空，返回ans即可。

c++链表反转。有要求

#includecstdio

#includecstdlib

struct Node{

char name[50];

int salary;

Node* next;

};

Node* createNode()

{

Node* lastnode = 0;

Node* head = 0;

int num;printf("请输入员工野凳的个数:");scanf("%d",num);

char buf[50];

for(int i=0;inum;++i)

{

Node* node = new Node;

printf("请输入员闹念工%d的名字液脊困:",i+1);scanf("%s",node-name);

printf("请输入员工%d的工资:",i+1);scanf("%s",buf);node-salary=atoi(buf);

if(lastnode!=0) lastnode-next=node; else head=node;

lastnode=node;

}

lastnode-next=0;

return head;

}

Node* reverseNode(Node* head)

{

Node* iter = head;

Node* lastiter = 0;

while(iter!=0)

{

Node* temp=iter-next;

iter-next=lastiter;

lastiter=iter;

iter=temp;

}

return lastiter;

}

Node* printNode(Node* head)

{

Node* iter = head;

while(iter!=0)

{

printf("员工的名字：%s 员工的工资：%d\n",iter-name, iter-salary);

iter=iter-next;

}

}

int main()

{

Node* head = createNode();

printNode(head);

printf("反转:\n");

Node* head2 = reverseNode(head);

printNode(head2);

return 0;

}

关于链表反转和java链表反转的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。