什么是链表
链表是用来存储数据集合的数据结构。有如下属性：
- 相邻元素通过指针连接
- 最后一个的后继指针为NULL
- 链表长度可以增加和缩小
- 空间按需分配，直至内存耗尽，但是存储指针会相对数组耗费一些额外空间
linkedlist
链表抽象数据结构
主要操作：
- 添加元素，
- 删除元素（移除并返回链表中指定位置的元素）
辅助操作：
- 获取元素个数
- 查询（寻找从链表表头开始的第n个结点），
- 清空元素
这里给出插入和删除的java代码示例：
/* time:O(n) space:O(1) */
public ListNode insertLinkedList(ListNode headNode, ListNode nodeToInsert, int positon){
if (headNode == null) {
return nodeToInsert;
}
if (nodeToInsert == null) {
return headNode;
}
//这里需要效验position是否在有效范围
if (position == 0) {
nodeToInsert.setNext(headNode);
return nodeToInsert;
}else {
ListNode previousNode = headNode;
for (int i = 1; i < positon; i++) {
previousNode = previousNode.getNext();
}
nodeToInsert.setNext(previousNode.getNext());
previousNode.setNext(nodeToInsert);
}
return headNode;
}
public ListNode deleteNodeFromLinkedList(ListNode headNode, int position){
if (position == 1) {
ListNode currentNode = headNode.getNext();
headNode = null;
return currentNode;
}else {
ListNode previousNode = headNode;
for (int i = 1; i < position; i++) {
previousNode = previousNode.getNext();
}
ListNode curNode = previousNode.getNext();
previousNode.setNext(curNode.getNext());
}
return headNode;
}
为什么用链表
数组一样能用来存储数据集合，那为什么用多种数据结构来做一样的事情。因为后来发现数组在处理一些情况下的弊端，所以开始分使用情景用不同的工具干同样的事情。
先说说数组在一些情况下的缺点，
- 大小是固定的，需要分配一块连续的空间块，就造成有时候无法分配能存储整个数组的内存空间（当数组规模太大时），（当然动态数组通过到达数组最大长度后再申请更大容量数组来加入新元素）大空间没有足量的元素也会造成空间的浪费。
- 基于位置的插入操作实现复杂，考虑最糟的一种情况，插入到数组开始的位置，就需要移动原有数组的每一个元素。
对数组，链表最大的有点在于在任何位置插入元素的时间开销仅为O(1)。然而查找某个元素的开销为O(n)。
链表、数组和动态数组的对比
linedlist_compare
双向链表与循环链表
双向链表是单项链表的拓展，就是加入指向前一个结点的指针，用NULL表示指针的结束。循环指针就是头指针指向尾结点地址，形成了一个贪吃蛇的形状，没有NULL指针，需要注意无限循环遍历，因为每一个结点都有后继结点。
eg: 用链表实现栈
public class ListNodeStack{
private ListNode headNode;
public ListNodeStack(){
this.headNode = new ListNode(null);
}
public void push(int data){
if(headNode == null){
headNode = new ListNode(data);
}else if(headNode.getData() == null){
headNode.setData(data);
}else {
ListNode node = new ListNode(data);
node.setNext(headNode);
headNode = node;
}
}
public void pop(){
if(isEmpty()){
throw new EmptyStackException("Stack empty");
}else {
int data = headNode.getData();
headNode = headNode.getNext();
return data;
}
}
public boolean isEmpty(){
return null == headNode;
}
public void deleteStack(){
headNode = null;
}
}
eg1：知道链表倒数第n个结点
/* space:O(1) , time:O(n)*/
public ListNode nthNodeFromEnd(ListNode head, int nthNode){
ListNode fast = head, slow = head;
for (int i = 1; i < nthNode; i++) {
if (fast != null) {
fast = fast.getNext();
}
}
while(fast != null) {
fast = fast.getNext();
slow = slow.getNext();
}
return slow;
}
eg2: 判定给定的链表是以NULL结尾，还是形成了一个环。
解决方法是经典的快慢指针法：试想一下乌龟和兔子在同一个轨道上赛跑。如果它们在同一个环上赛跑，那么跑得快的兔子将赶上跑得慢的乌龟，并在某一点相遇。
image
image
public boolean doesLinkedListContainerLoop(ListNode head){
if (head == null) {
return false;
}
LsitNode fastPtr = head, slowPtr = head;
while (fastPtr != null && fastPtr.getNext() != ll) {
fastPtr = fastPtr.getNext().getNext();
slowPtr = slowPtr.getNext();
if (fastPtr == slowPtr) {
return true;
}
}
return false;
}
eg3:逆置单向列表
public ListNode reverseListUsingRecursion(ListNode head){
if (head == null || head.getNext() == null) {
return head;
}
ListNode newHead = reverseListUsingRecursion(head.getNext());
head.getNext().setNext(head);
head.setNext(null);
return newHead;
}
迭代版本
public ListNode reverseList(ListNode head){
ListNode tmp = null, nextNode = null;
while (head != null){
nextNode = head.getNext();
head.setNext(tmp);
tmp = head;
head = nextNode;
}
return tmp;
}
eg4: 逆置链表，两个为单位进行逆置，eg：1->2->3->4->x => 2->1->4->3->x
//space:o(n), time:O(n)
public ListNode reversePairRecursive(ListNode head) {
ListNode temp;
if (head == null || head.getNext() == null) {
return head;
}
temp = head.getNext();
head.setNext(temp.getNext());
temp.setNext(head);
head = temp;
head.getNext().setNext(reversePairRecursive(head.getNext().getNext()));
return head;
}
迭代版本代码：
/* space:o(1), time:O(n) */
public ListNode reversePairIterative(ListNode head) {
ListNode temp1 = null;
ListNode temp2 = null;
while (head != null && head.getNext() != null) {
if (temp1 != null) {
temp1.next().setNext(head.getNext());
}
temp1 = head.getNext();
head.setNext(temp1.getNext());
temp1.setNext(head);
if (temp2 == null) {
temp2 = temp1;
}
head = head.getNext();
}
return temp2;
}
eg5: 逆置链表，k个为单位进行逆置，eg：1 2 3 4 5 6 7 8 9 10 , k=3: 3 2 1 6 5 4 9 8 7 10
public ListNode getKPlusOneThNode(int k, ListNode head) {
ListNode kNode = head;
if (head == null) {
return head;
}
for (int i = 1; kNode != null && (i <= k); i++, kNode = kNode.getNext()) {
if (k == i) {
return kNode;
}
}
return head.getNext();
}
public boolean hasKNode(ListNode head, int k) {
if (head == null) {
return head;
}
for (int i = 1; head != null && (i <= k); i++, head = head.getNext()) {
if (i == k) {
return true;
}
}
return false;
}
public ListNode reverseBolckOf(ListNode head, int k) {
ListNode newHead, curNode, temp, next;
curNode = head;
if (k ==0 || k == 1) {
return head;
}
if (hasKNode(head, k)) {
newHead = getKPlusOneThNode(k, head);
}else {
newHead = head;
}
while (curNode != null && hasKNode(curNode, k)) {
temp = getKPlusOneThNode(k, curNode);
int i = 0;
while (i < k) {
next = curNode.getNext();
curNode.setNext(temp);
temp = curNode;
curNode = next;
i++;
}
}
return newHead;
}
网友评论