链表(Linked List)

在刷题的时候顺便把涉及到知识复习整理到博客,慢慢把本地的笔记转移到博客上来

介绍

链表是有序的列表

链表是以节点的方式来存储,是链式存储每个节点包含 data域 next域:指向下一个节点链表的各个节点不一定是连续存储链表分带头节点和没有头节点的链表

添加节点

创建一个head头节点,表示单链表的头后面每增加一个节点,直接加到链表的最后将节点插入到指定位置 (1). 借助辅助变量(temp;指针)通过遍历找到新的节点位置 (2). 新的节点.next = temp.next (3). temp.next = 新的节点

删除节点

找到需要删除的节点的前一个节点temptemp.next = temp.next.next被删除的节点无其他引用指向,会被垃圾回收机制回收

单链表面试题

求单链表有效节点的个数

思路:

判断head.next是否为空 空返回0;初始化一个变量int length = 0;定义一个辅助变量cur = head.nextcur不为空(使用while) length++ cur指向cur的下一个节点cur为空返回length即可

求单链表的倒数第k个节点

思路:

编写一个方法接收head 节点 同时接收index(表示倒数第index节点)链表从头到尾表里,得到链表的总的长度 getLength从链表的第一个开始遍历(总长度-index)个找到返回节点 否则返回null;

单链表的反转

思路:

先定义一个节点reverseHead = new ListNode();定义辅助指针(当前指针curr,下一个指针next),帮助遍历原来的链表从头到尾遍历原来的链表,每遍历一个链表,就将其取出,放在新的链表的最前端只要curr不为空 next=cur.next , curr.next=reverseHead.next, reverseHead.next.next=curr, cur=next原来链表的head.next=reverseHead.next这里把next想象成指针比较好理解

(所有的题目先判断链表是否为空,空直接返回结果)

从尾到头打印单链表

思路:

方式一: 反向遍历

见上一题,反转链表后遍历,这样做破坏原有链表结构

方式二: Stack

判断列表为空的情况创建一个栈 Stack使用push方法把所有节点压入栈只要stack长度大于0,使用pop取出元素打印

双向链表

双向链表可以双向打印双向链表可以自我删除 不需要辅助指针

单向环形链表

需要辅助指针

资料参考:尚硅谷