最近在总结数据结构的过程中，遇到了链表这一基本数据结构，先对此有个大致的了解吧。本文的很多内容都是参考博主sean-zou的博客http://blog.csdn.net/a19881029/article/details/22695289和jianyuerensheng的http://blog.csdn.net/jianyuerensheng/article/details/51200274特此说明。时间是2017.7.31
基本结构
链表是一种数据结构，和数组同级。比如，Java中我们使用的集合类ArrayList，其实现原理是数组。而LinkedList的实现原理就是链表了。链表在进行循环遍历时效率不高，但是插入和删除时优势明显。
单向链表是一种线性表，实际上是由节点（Node）组成的，一个链表拥有不定数量的节点。其数据在内存中存储是不连续的（而数组在内存中是连续的），它存储的数据分散在内存中，每个结点只能也只有它能知道下一个结点的存储位置。由N各节点（Node）组成单向链表，每一个Node记录本Node的数据及下一个Node。向外暴露的只有一个头节点（Head），我们对链表的所有操作，都是直接或者间接地通过其头节点来进行的。
上图中最左边的节点即为头结点（Head），但是添加节点的顺序是从右向左的，添加的新节点会被作为新节点。最先添加的节点对下一节点的引用可以为空。引用是引用下一个节点而非下一个节点的对象。因为有着不断的引用，所以头节点就可以操作所有节点了。
下图描述了单向链表存储情况。存储是分散的，每一个节点只要记录下一节点，就把所有数据串了起来，形成了一个单向链表。
节点（Node）是由一个需要储存的对象及对下一个节点的引用组成的。也就是说，节点拥有两个成员：储存的对象、对下一个节点的引用。下面图是具体的说明：
基本操作
1，insertFirst：在表头插入一个新的链接点，时间复杂度为O(1)
2，deleteFirst：删除表头的链接点，时间复杂度为O(1)
有了这两个方法，就可以用单链表来实现一个栈了，见http://blog.csdn.net/a19881029/article/details/22579759
3，find：查找包含指定关键字的链接点，由于需要遍历查找，平均需要查找N/2次，即O(N)
4，remove：删除包含指定关键字的链接点，由于需要遍历查找，平均需要查找N/2次，即O(N)
代码实现
创建节点类
package linkedlist;
public class Node {
Node next = null;// 节点的引用，指向下一个节点
int data;// 节点的数据，即内容
public Node(int data) { //构造方法，用于初始化数据data
this.data = data;
}
}
对节点进行插入和删除操作
package linkedlist;
public class MyLink {
Node head = null; // 初始化头节点
/** * 打印当前链表 * */
public void printList() {
Node tmp = head;
while (tmp != null) {
System.out.print(tmp.data + " ");
tmp = tmp.next;
}
}
/** * * @return 返回节点长度 */
public int length() {
int length = 0;
Node tmp = head;
while (tmp != null) {
length++;
tmp = tmp.next;
}
return length;
}
/** * 向链表中插入数据,直接插到尾节点后边 * * @param d */
public void addNode(int d) {
Node newNode = new Node(d);// 实例化一个节点
if (head == null) {
head = newNode;
return;
}
// =============以上情况表示插入的节点如果是紧紧跟在头结点后边的一个====//
Node tmp = head;
while (tmp.next != null) {
tmp = tmp.next;
}
tmp.next = newNode;
}
/** * * @param index * :删除第index个节点 * @return */
public boolean deleteNode(int index) {
if (index < 1 || index > length()) { // 如果要删除的节点不在该链表上
return false;
}
if (index == 1) { // 如果要删除的是头结点
head = head.next;
return true;
}
int i = 2;
Node preNode = head; // 前一个节点，初始化为头节点
Node curNode = preNode.next; // 当前节点，也就是前一个节点的下一个，初始化为头节点的下一个节点
while (curNode != null) { // 如果当前节点不是空
if (i == index) { // 找到要删除的索引标号了
preNode.next = curNode.next;// 让前一个的下一个指向我的下一个，也就是让我消失了
return true;
}
preNode = curNode;
curNode = curNode.next; // 如果没找到，前节点和当前节点均向后移动一位
i++; // 总之就是让i的数字等于当前节点cur的标识，也就是两个箭头指向同一个节点
}
return false;
}
/** * 在不知道头指针的情况下删除指定节点 * * @param n * @return */
public boolean deleteNode11(Node n) {
if (n == null || n.next == null)
return false;
int tmp = n.data;
n.data = n.next.data;
n.next.data = tmp; // 交换指定节点和指定节点下一个节点的数据，此时，指定节点里的引用虽然仍然指向下一个节点看，但数据已经是下一节点的了
n.next = n.next.next; // 删除指定节点的下一节点（下一节点里的数据放的其实是指定节点的）
System.out.println("删除成功！"); // 为什么要这么做呢，因为每个节点存的索引只有指向下一个的，要想删除必须让自己的前一个指向自己的下一个，但你不知道自己上一个，所以只能用交换数据的方式。
return true;
}
public static void main(String[] args) {
MyLink list = new MyLink();
list.addNode(5);
list.addNode(3);
list.addNode(1);
list.addNode(2);
list.addNode(55);
list.addNode(36);
System.out.println("linkLength: " + list.length());//linkLength: 6
System.out.println("head.data: " + list.head.data);//head.data: 5
list.printList();//5 3 1 2 55 36
list.deleteNode(4);
System.out.println("After deleteNode(4): ");
list.printList();//After deleteNode(4): 5 3 1 55 36
}
}
进阶操作（面试常考）
链表反转
/** * 链表反转 * * @param head * @return */
public Node ReverseIteratively(Node head) {
if (head == null) {
return null;
} // 当传入的节点为null的时候，直接返回null。如果只有一个节点，头尾都是它，直接返回该节点
Node pReversedHead = head;
Node pNode = head; // 当前节点，并让它指向传进来的对象所在地址
Node pPre = null; // 当前节点的前一个节点
Node pNext = null; // 当前节点的后一个节点
while (pNode != null) {
pNext = pNode.next; // 用pNext存储原链表中节点指向的下一个节点
if (pNext == null) { // 如果当前节点的下一个节点为空，说明pNode是最后一个节点
pReversedHead = pNode; // 让反转头节点指向当前链表尾节点
}
pNode.next = pPre; // 核心，当前节点的下一个变成了上一个，完成了反转
pPre = pNode;
pNode = pNext; // 向后移动节点继续进行反转
}
this.head = pReversedHead;
return this.head;
}从尾到头打印链表
采用递归方式实现
/** * 从尾到头输出单链表，采用递归方式实现 * * @param pListHead */
public void printListReversely(Node pListHead) {
if (pListHead != null) {
printListReversely(pListHead.next); //递归调用该函数，只要不为空一直向里调用，最后发现最先打印出来的是最后一个
System.out.println("printListReversely:" + pListHead.data);
}
}在一个已经排序的列表中删除重复节点
/** * 在一个排序的列表中删除重复的节点 */
public Node deleteSortDuplecate(Node head) {
Node first = new Node(-1);
first.next = head;
Node pre = first;
Node p = head;
while (p != null) {
if (p.data == p.next.data) {
int val = p.data;
while (p != null && p.data == val) {
p = p.next;
}
pre.next = p;
} else {
pre = p;
p = p.next;
}
}
return first.next;
}找出单链表倒数第k个节点
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null||k<=0){
return null;
}
ListNode p1 = head;
ListNode p2 = head;
for (int i = 1; i < k; i++) {
if(p1.next!=null) //防止给出的k大于节点长度，如果下一个为null则大于
p1=p1.next;
else
return null;
}
while(p1.next!=null){ //p1先走k-1步，到时候p1到底的时候，p2刚好在倒数第k个节点处
p1 = p1.next;
p2 = p2.next;
}
return p2;
}合并两个递增链表，合并后仍为递增
public static Node Merge(Node head1, Node head2) {
if(head1==null){
return head2;
}
if(head2==null){
return head1;
}
Node p1 = head1;
Node p2 = head2;
Node newHead = p2;
if (p1.val <= p2.val) {
newHead = p1;
p1 = p1.next;
} else {
newHead = p2;
p2 = p2.next;
}
Node temp = newHead;
while (p1 != null && p2 != null) { //都不是尾节点的时候一个一个判断
if (p1.val <= p2.val) {
temp.next = p1;
p1 = p1.next;
} else {
temp.next = p2;
p2 = p2.next;
}
temp = temp.next;
}
if(p1==null){ //p1到尾了，直接把p2和以后的挂上
temp.next = p2;
}
if(p2==null){
temp.next=p1;
}
return newHead;
}判断链表是否有环，有环情况下找出环的入口节点
使用追赶的方法，设定两个指针slow、fast，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。
/** * 判断链表是否有环，单向链表有环时，尾节点相同 * * @param head * @return */
public boolean IsLoop(Node head) {
Node fast = head, slow = head;
if (fast == null) {
return false;
}
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
System.out.println("该链表有环");
return true;
}
}
return !(fast == null || fast.next == null);
}
有定理：碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。
/** * 找出链表环的入口 * * @param head * @return */
public Node FindLoopPort(Node head) {
Node fast = head, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast)
break;
}
if (fast == null || fast.next == null)
return null;
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}查找单链表的中间节点
采用快慢指针的方式查找单链表的中间节点，快指针一次走两步，慢指针一次走一步，当快指针走完时，慢指针刚好到达中间节点。
/** * 查找单链表的中间节点 * * @param head * @return */
public Node SearchMid(Node head) {
Node p = this.head, q = this.head;
while (p != null && p.next != null && p.next.next != null) {
p = p.next.next;
q = q.next;
}
System.out.println("Mid:" + q.data);
return q;
}对链表进行排序
/** * 排序 * * @return */
public Node orderList() {
Node nextNode = null;
int tmp = 0;
Node curNode = head;
while (curNode.next != null) {
nextNode = curNode.next;
while (nextNode != null) {
if (curNode.data > nextNode.data) {
tmp = curNode.data;
curNode.data = nextNode.data;
nextNode.data = tmp;
}
nextNode = nextNode.next;
}
curNode = curNode.next;
}
return head;
}找出两个链表的公共节点
第一个的尾指向第二个的头
先遍历第一个链表到他的尾部，然后将尾部的next指针指向第二个链表(尾部指针的next本来指向的是null)。这样两个链表就合成了一个链表，判断原来的两个链表是否相交也就转变成了判断新的链表是否有环的问题了：即判断单链表是否有环？
public ListNode EntryNodeOfLoop(ListNode pHead)
{
if(pHead==null){
return null;
}
ListNode fast = pHead;
ListNode slow = pHead;
if(fast ==null || fast.next == null){
return null;
}
while(fast != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
break;
}
}
slow = pHead;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}这样问题就转换为了求环的入节点，以上代码在oj测试的时候显示超时，所以还是用下边的方法吧
暴力遍历法
public ListNode FindFirstCommonNodeII(ListNode pHead1, ListNode pHead2) {
ListNode current1 = pHead1;// 链表1
ListNode current2 = pHead2;// 链表2
if (pHead1 == null || pHead2 == null)
return null;
int length1 = getLength(current1);
int length2 = getLength(current2);
// 两连表的长度差
// 如果链表1的长度大于链表2的长度
if (length1 >= length2) {
int len = length1 - length2;
// 先遍历链表1，遍历的长度就是两链表的长度差
while (len > 0) {
current1 = current1.next;
len--;
}
}
// 如果链表2的长度大于链表1的长度
else if (length1 < length2) {
int len = length2 - length1;
// 先遍历链表1，遍历的长度就是两链表的长度差
while (len > 0) {
current2 = current2.next;
len--;
}
}
//开始齐头并进，直到找到第一个公共结点
while(current1!=current2){
current1=current1.next;
current2=current2.next;
}
return current1;
}
// 求指定链表的长度
public static int getLength(ListNode pHead) {
int length = 0;
ListNode current = pHead;
while (current != null) {
length++;
current = current.next;
}
return length;
}HashMap法
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode current1 = pHead1;
ListNode current2 = pHead2;
HashMap<ListNode, Integer> hashMap = new HashMap<ListNode, Integer>();
while (current1 != null) {
hashMap.put(current1, null);
current1 = current1.next; //遍历把链表1中的所有节点当成key，在hashmap中key不能重复，为什么不用set，因为set没有判断key是否包含的方法。
}
while (current2 != null) {
if (hashMap.containsKey(current2))
return current2; //如果有相同的key就是第一个公共节点，返回
current2 = current2.next;
}
return null;
}复杂链表的复制
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
public class Solution {
public RandomListNode Clone(RandomListNode pHead){
if(pHead==null)
return null;
RandomListNode pCur = pHead;
第一步 //复制next 如原来是A->B->C 变成A->A'->B->B'->C->C'
while(pCur!=null){
RandomListNode node = new RandomListNode(pCur.label);
node.next = pCur.next;//A'指向B
pCur.next = node;//A指向A'
pCur = node.next;//当前指针跳转到B
}
pCur = pHead; //当前指针指回头节点
===================================================================
第二步：让复制后的任意指向也满足之前的规律
//复制random pCur是原来链表的结点 pCur.next是复制pCur的结点
while(pCur!=null){
if(pCur.random!=null)
pCur.next.random = pCur.random.next;
pCur = pCur.next.next;
}
//创建新链表的头节点和移动指针，归位原链表的移动指针
RandomListNode head = pHead.next;
RandomListNode cur = head;
pCur = pHead;
=================================================================
第三步:拆分链表
while(pCur!=null){
pCur.next = pCur.next.next; //原链表抽离
if(cur.next!=null)
cur.next = cur.next.next; //新链表抽离
cur = cur.next;
pCur = pCur.next;
}
return head; //返回复制后的新链表的头节点
第三步的代码不能写为
while(pCur!=null && cur.next!=null){
pCur.next = pCur.next.next; //原链表抽离
cur.next = cur.next.next; //新链表抽离
cur = cur.next;
pCur = pCur.next;
}
写成这样的话，到最后一步的时候，pCur ！= null 条件还为真，但后边已经为假，这样最后一个E-E'就拆不开了。
京公网安备 11010502036488号