数据结构---链表

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;
}
}
全部评论

相关推荐

11-07 11:46
已编辑
南京理工大学 C++
都没出结果,问问是各位会如何选择补充一下,华为应该是14左右县是南通市下面的一个县局
在敲键盘的布莱克很积极:兄弟,我给你提供一个角度,其他评论可能更多是从待遇和发展前景来看的,但是我建议你想一想你走哪条路更能产生对自己的身份认同。 如果你乐于钻研技术,喜欢工程实践,即使从华为失业你也能认可自己工程师的身份,不因为工作上不顺而失去对自己的尊重(因为这是你几乎必然会面对的情况),那就可以去华为,毕竟广阔天地大有可为。 但是如果你并不能因为技术产生自我的身份认同,那建议还是公务员吧,因为这种职业自带身份认同,不需要你有很强的兴趣与心理建设来支持,即使每月钱不多,你比较容易做到自己尊重自己,也容易在社会上得到他人的尊重。 不管钱多钱少,待遇怎么样,最终还是要自己过得开心,享受到了生活,才算是好的一生
投递华为等公司10个岗位 >
点赞 评论 收藏
分享
11-01 20:03
已编辑
门头沟学院 算法工程师
Amazarashi66:这种也是幸存者偏差了,拿不到这个价的才是大多数
点赞 评论 收藏
分享
11-05 07:29
贵州大学 Java
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务