1、链表结构概述
- 链表是一种物理存储单元上非连续、非顺序的存储结构,其物理结构不能只管的表示数据元素的逻辑顺序,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列的结点(链表中的每一个元素称为结点)组成,结点可以在运行时动态生成。
例题一:反转链表
1、栈实现
- 因为栈是先进后出的。实现原理就是把链表节点一个个入栈,当全部入栈完之后再一个个出栈,出栈的时候在把出栈的结点串成一个新的链表,最后返回新链表的头节点
import java.util.Stack;
public class Solution {
public ListNode ReverseList(ListNode head) {
Stack<ListNode> stack= new Stack<>();
//把链表节点全部摘掉放到栈中
while (head != null) {
stack.push(head);
head = head.next;
}
if (stack.isEmpty())
return null;
ListNode node = stack.pop();
ListNode newhead = node;
//栈中的结点全部出栈,然后重新连成一个新的链表
while (!stack.isEmpty()) {
ListNode tempNode = stack.pop();
node.next = tempNode;
node = node.next;
}
//最后一个结点就是反转前的头结点,一定要让他的next
//等于空,否则会构成环
node.next = null;
return newhead;
}
}
2、双链表求解
- 双链表求解是把原链表的结点一个个摘掉,每次摘掉的链表都让他成为新的链表的头结点,然后更新新链表。
public class Solution {
public ListNode ReverseList(ListNode head) {
//新链表
ListNode newHead = null;
while (head != null) {
//先保存访问的节点的下一个节点,保存起来
//留着下一步访问的
ListNode temp = head.next;
//每次访问的原链表节点都会成为新链表的头结点,
//其实就是把新链表挂到访问的原链表节点的
//后面就行了
head.next = newHead;
//更新新链表
newHead = head;
//重新赋值,继续访问
head = temp;
}
//返回新链表
return newHead;
}
}