LinkedList与链表

1.链表的引入

由于在ArrayList任意位置插入或者删除元素时就需要将元素整体往前或者往后搬移，时间复杂度为O（n），效率比较低，因此ArrayList不适合在任意位置插入或者删除元素，因此引入了LinkedList，即链表结构。

2.链表的分类

2.1 单向或者双向

无头指每一个节点都可以存放数字

2.2 带头或者不带头

2.3 循环或者非循环

无头单向非循环结构简单，作为其他数据结构的子结构，在笔试面试中出现的比较多

同时，无头双向循环链表，为LinkedList底层实现的链表。

3.链表的实现（无头单项非循环）

import java.util.LinkedList;public class MyLinkedList implements IList{static class ListNode {public int val;public ListNode preV;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;//这里的head并不是指头而是方便取的名字public ListNode last;@Overridepublic void addFirst(int data) {ListNode cur = head;ListNode node = new ListNode(data);if(head.next == null){head = last = node;}else{node.next = cur;cur.preV = node;head = node;}}@Overridepublic void addLast(int data) {ListNode cur = head;ListNode node = new ListNode(data);if(head == null) {head = last = node;}else{last.next = node;node.preV = last;last = node;}}@Override//在指定位置增删元素public void addIndex(int index, int data) {int len = size();if(index < 0 || index > len ){System.out.println("不符合条件");return;}if(index == 0){addFirst(index);return;}if(index == len){addLast(data);return;}else{ListNode cur = findOfKey(index);ListNode node = new ListNode(data);node.next = cur;node.preV = cur.preV;cur.preV.next = node;cur.preV = node;}}private ListNode findOfKey(int index){ListNode cur = head;while(index != 0){cur = cur.next;index--;}return cur;}@Overridepublic boolean contains(int key) {ListNode cur = head;while(cur != null){if(cur.val == key){return true;}cur = cur.next;}return false;}@Overridepublic void remove(int key) {ListNode cur = head;while(cur != null) {if (cur.val == key) {if (cur == head) {head = head.next;if (head != null) {head.preV = null;}} else {cur.preV.next = cur.next;if ( cur.next == null) {last = last.preV;}else {cur.next.preV = cur.preV;}}}cur =cur.next;}}@Overridepublic void removeAllKey(int key) {ListNode cur = head;while(cur != null) {if (cur.val == key) {if (cur == head) {head = head.next;if (head != null) {head.preV = null;}}else {cur.preV.next = cur.next;if (cur.next == null) {last = last.preV;}cur.next.preV = cur.preV;}}cur = cur.next;}}@Overridepublic int size() {ListNode cur = head;int len = 0;while(cur != null){len++;cur = cur.next;}return len;}@Overridepublic void clear() {ListNode cur = head;if(cur != null){ListNode curN = cur.next;cur.preV = null;cur.next = null;cur = curN;}head = null;last = null;}@Overridepublic void display() {ListNode cur = head;while(cur != null){System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}

接口：

public interface IList {public void addFirst(int data);public void addLast(int data);public void addIndex(int index,int data);public boolean contains (int key);public void remove(int key);public void removeAllKey(int key);public int size();public void clear();public void display();}

4.链表面试题

4.1 移除链表元素

 public class Solution {public ListNode removeElements(ListNode head, int val) {if(head == null){return head;}ListNode pre = head;ListNode cur = head.next;while(cur != null){if(cur.val == val){pre.next = cur.next;cur = cur.next;}else{pre = cur;cur = cur.next;}}if(head.val == val){head = head.next;}return head;}}

4.2 反转链表

class Solution {public ListNode reverseList(ListNode head) {if(head == null){return head;}ListNode cur = head.next;head.next = null;while(cur != null){ListNode curN = cur.next;cur.next = head;head = cur;cur = curN;}return head;}
}

4.3 链表的中间结点

class Solution {public ListNode middleNode(ListNode head) {if(head == null){return head;}ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}return slow;}
}

4.4 返回倒数第k个节点

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public int kthToLast(ListNode head, int k) {if(head == null){return head.val;}ListNode fast = head;ListNode slow = head;int count = k - 1;while(count != 0){fast = fast.next;count--;}while(fast.next != null){fast = fast.next;slow = slow.next;}return slow.val;}
}

4.5 合并两个有序链表

 /*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode newHead = new ListNode(-1);ListNode tmp = newHead;while(list1 != null && list2 != null){if(list1.val <= list2.val){tmp.next = list1;list1 = list1.next;tmp = tmp.next;}else{tmp.next = list2;tmp = tmp.next;list2 = list2.next;}}if(list1 != null){tmp.next = list1;}if(list2 != null){tmp.next = list2;}return newHead.next;}
}

4.6 链表分割

public class Partition {public ListNode partition(ListNode pHead, int x) {ListNode as = null;ListNode ae = null;ListNode bs = null;ListNode be = null;ListNode cur = pHead;while(cur != null){if(cur.val < x){if(as == null){as = ae = cur;}else{ae.next = cur;ae = ae.next;}}else{if(bs == null){bs = be =cur;}else{be.next = cur;be = be.next;}}cur = cur.next;}if(as == null){return bs;}ae.next = bs;if(bs != null){be.next = null;}return as;}}

4.7 链表回文

public class PalindromeList {public boolean chkPalindrome(ListNode A) {if(A == null){return false;}// write code hereListNode fast = A;ListNode slow = A;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}ListNode cur = slow.next;while(cur !=  null){ListNode curN = cur.next;cur.next = slow;slow = cur;cur = curN;}while(A != slow){if(A.val != slow.val){return false;}if(A.next == slow){return true;}A= A.next;slow = slow.next;}return true;}
}

4.8 相交链表

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pl = headA;ListNode ps = headB;int lenA = 0;int lenB = 0;//计算长度while(pl != null){lenA++;pl = pl.next;}while(ps != null){lenB++;ps = ps.next;}pl = headA;ps = headB;//计算两个链表的差值int len = lenA - lenB;if(len < 0){pl = headB;ps = headA;len = lenB - lenA;}while(len != 0){pl = pl.next;len--;}while(pl != ps){pl = pl.next;ps = ps.next;}if(pl == null){return null;}return pl;}
}

4.9 环形链表

public class Solution {public boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast  ==  slow ){return true;}}return false;}
}

5.双向链表的基本实现（LinkedList）

public class MyLinkedList implements IList{static class ListNode {public int val;public ListNode preV;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode last;@Overridepublic void addFirst(int data) {ListNode cur = head;ListNode node = new ListNode(data);if(head.next == null){head = last = node;}else{node.next = cur;cur.preV = node;head = node;}}@Overridepublic void addLast(int data) {ListNode cur = head;ListNode node = new ListNode(data);if(head == null) {head = last = node;}else{last.next = node;node.preV = last;last = node;}}@Override//在指点位置增删元素public void addIndex(int index, int data) {int len = size();if(index < 0 || index > len ){System.out.println("不符合条件");return;}if(index == 0){addFirst(index);return;}if(index == len){addLast(data);return;}else{ListNode cur = findOfKey(index);ListNode node = new ListNode(data);node.next = cur;node.preV = cur.preV;cur.preV.next = node;cur.preV = node;}}private ListNode findOfKey(int index){ListNode cur = head;while(index != 0){cur = cur.next;index--;}return cur;}@Overridepublic boolean contains(int key) {ListNode cur = head;while(cur != null){if(cur.val == key){return true;}cur = cur.next;}return false;}@Overridepublic void remove(int key) {ListNode cur = head;while(cur != null) {if (cur.val == key) {if (cur == head) {head = head.next;if (head != null) {head.preV = null;}} else {cur.preV.next = cur.next;if ( cur.next == null) {last = last.preV;}else {cur.next.preV = cur.preV;}}}cur =cur.next;}}@Overridepublic void removeAllKey(int key) {ListNode cur = head;while(cur != null) {if (cur.val == key) {if (cur == head) {head = head.next;if (head != null) {head.preV = null;}}else {cur.preV.next = cur.next;if (cur.next == null) {last = last.preV;}cur.next.preV = cur.preV;}}cur = cur.next;}}@Overridepublic int size() {ListNode cur = head;int len = 0;while(cur != null){len++;cur = cur.next;}return len;}@Overridepublic void clear() {ListNode cur = head;if(cur != null){ListNode curN = cur.next;cur.preV = null;cur.next = null;cur = curN;}head = null;last = null;}@Overridepublic void display() {ListNode cur = head;while(cur != null){System.out.print(cur.val+" ");cur = cur.next;}System.out.println();}//在指定位置进行打印public void display2(ListNode newHead) {ListNode cur = head;while (cur != null) {System.out.print(cur.val + " ");cur = cur.next;}System.out.println();}public ListNode reverseList() {if(head == null){return head;}ListNode cur = head.next;head.next = null;while(cur != null){ListNode curN = cur.next;cur.next = head;head = cur;cur = curN;}return head;}}