<svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path> </svg> <p><strong>链表的概念及结构：</strong></p> 讯享网
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
虽然有这么多的链表的结构，但是我们重点掌握两种:
无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希图、图的邻接表等等。另外这种结构在笔试面试中出现很多。
今天要解的问题就是如何原地逆转一个无头单向非循环链表：
PS：只能遍历一遍单链表
第一种方法头插法
思想：
是只要head.next不为空，就将find = head.next 调用头插方法插到链表的第一个位置。
public class ListNode {
public int date;
public ListNode next;
public ListNode(int date) {
this.date = date;
}
}
public class MyLinkList {
private ListNode phead;
public MyLinkList() {
this.phead = null;
}
public void addFirst(int data){
ListNode node = new ListNode(data);
if(this.phead == null) {
//第一次插入节点
this.phead = node;
return;
}
node.next = this.phead;
this.phead = node;
}
public ListNode reserveLinkList() {
if(this.phead == null) {
return null;
}
if(this.phead.next == null) {
return this.phead;
}
ListNode find = this.phead.next;
this.phead.next = null;
while (find != null) {
ListNode findNext = find.next;
addFirst(find.date);
find = findNext;
}
return this.phead;
}
public void display2(ListNode head) {
ListNode find = head;
while (find != null) {
System.out.print(find.date + “ ”);
find = find.next;
}
System.out.println();
}
}
public class Test {
public static void main(String[] args) {
MyLinkList link = new MyLinkList();
link.addLast(10);
link.addLast(20);
link.addLast(30);
link.addLast(40);
link.addLast(50);
link.addLast(60);
link.display();
link.display2(link.reserveLinkList());
}
}
代码运行结果：
10 20 30 40 50 60
60 50 40 30 20 10
方法二 尾接法
思想：定义三个连续的节点，指向单链表连续的三个位置，将前俩个反转，然后三个节点依次往下一个节点走。
Ps：一定要将反转后的单链表的最后一个节点的next = null。
public class Node {
public int date;
public Node next;
public Node(int date) {
this.date = date;
}
}
public class LinkList {
private Node head;
public LinkList() {
this.head = null;
}
public Node reserveLinkList() {
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/195506.html