【算法】-- 【单链表的反转、增删、去重、中间节点、是否有环、有环的第一个节点、是否相交等】

1.定义一个数据类来存储节点信息

public class Node { Node next = null; int data; public Node(int data){ this.data=data; } }

2.单链表的基本操作

public class MyLinkedList { Node head = null; //链表表头的引用 /** * 向链表中插入数据 * @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 * @return 成功返回true 失败返回false */ 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.next!=null){ if (i == index){ preNode.next = curNode.next; return true; } preNode = curNode; curNode = curNode.next; i++; } return true; } /** * 返回节点的长度 * @return */ public int length(){ int length = 0; Node tmp = head; while (tmp.next!=null){ length++; tmp = tmp.next; } return length; } /** * 对链表进行排序 * @return */ public Node orderNode(){ Node nextNode = null; int temp =0; Node curNode = head; while (curNode.next!=null){ nextNode =curNode.next; while (nextNode != null){ if (curNode.data > nextNode.data){ temp = curNode.data; curNode.data = nextNode.data; nextNode.data = temp; } nextNode = nextNode.next; } curNode = curNode.next; } return head; } /** * 打印链表 */ public void printList(){ Node tmp = head; while(tmp!=null){ System.out.println(tmp.data); tmp = tmp.next; } } public static void main(String[] args) { MyLinkedList list = new MyLinkedList(); list.addNode(5); list.addNode(3); list.addNode(1); list.addNode(3); System.out.println("listLength: "+list.length()); System.out.println("before order:"); list.printList(); list.orderNode(); System.out.println("after order:"); list.printList(); } }

3.去掉重复的数据

Hashtable法，通过key键去掉重复的数据 /** * 去重 * @param head */ public void deleteDuplecate(Node head){ Hashtable<Integer,Integer> table = new Hashtable<>(); Node tmp = head; Node preNode = null; while(tmp!=null){ if (table.containsKey(tmp.data)){ preNode.next = tmp.next; }else{ table.put(tmp.data,1); preNode = tmp; } tmp=tmp.next; } } 对链表双重循环，外层进行正常循环，内层循环进行比较，如果于外层相同，就删掉 /** * 去重 * @param head */ public void deleteDuplecate1(Node head){ Node p = head; while(p!=null){ Node q = p; while(q.next!=null){ if (p.data == q.next.data){ q.next = q.next.next; }else{ q=q.next; } } p=p.next; } }

4.找出单链表中的倒数第k个元素

设置两个指针，让其中一个先前移k-1步，然后两个指针同时往前移动。直到先行的指针指到null，另一个就指到k。

/** * 找出单链表中倒数第k个元素 * @param head * @param k * @return */ public Node findElem(Node head, int k){ if (k<1) return null; Node p1 =head; Node p2 =head; for (int i=0;i<k-1&&p1!=null;i++) p1=p1.next; if (p1==null){ System.out.println("k不合法！"); return null; } while (p1.next!=null){ p1=p1.next; p2=p2.next; } return p2; }

5.链表的反转

/** * 链表反转 * @param head */ public void ReverseIteratively(Node head){ Node pReversedHead = head; Node pNode = head; Node pPrev = null; while(pNode !=null){ Node pNext = pNode.next; if (pNext==null){ pReversedHead = pNode; } pNode.next = pPrev; pPrev = pNode; pNode = pNext; } this.head = pReversedHead; }

6.从尾到头输出单链表

用递归的方法实现的

/** * 从尾到头输出单链表 * @param pListHead */ public void printListReversely(Node pListHead){ if (pListHead != null){ printListReversely(pListHead.next); System.out.println(pListHead.data); } }

7.查找单链表的中间节点

设置两个指针从头遍历，一个快指针走两步，一个慢指针走一步。快指针走到头，慢指针恰好到中间节点

/** * 寻找单链表的中间节点 * @param head * @return */ public Node searchMid(Node head){ Node p =head; Node q =head; while(p!= null && p.next!=null &&p.next.next!=null){ p = p.next.next; q = q.next; } return q; }

8.检查一个链表是否有环及找出第一个入环口

设置两个指针，fast快指针，走两步，slow慢指针，走一步。比较两个指针的值是否相等。当fast与slow的值相同，测试循环链表

/** * 检测一个链表是否有环 * @param head * @return */ public boolean isLoop(Node head){ Node fast = head; Node slow = head; if (fast==null){ return false; } while(fast!=null && fast.next!=null){ fast = fast.next.next; slow = slow.next; if (fast.data==slow.data){ return true; } } return !(fast==null || fast.next==null); }

如何找到环的入口点呢？ 如果单链表有环，按照上述思路，当走的快的指针fast与走的慢的指针slow相遇时，slow指针肯定没有遍历完链表，而fast指针已经在环内循环了n圈 ( n > = 1)。假设slow指针走了 s 步，则fast 指针走了 2s 步 （fast步数还等于 s 加上在环内多转的 n 圈），设环长为 r ，满足如下关系表达式： 2s = s + nr； s = nr； 设整个链表长L，入口环与相遇点距离 x ，起点到环入口点的距离为a，则满足如下关系表达式： a + s = nr； a + s = （n - 1）r + r = （n - 1）r + L - a ; a = （n - 1）r + （L - a - x）; （L - a - x）为相遇点到环入口点的距离，从链表头到环入口点等于（n - 1）循环内环+ 相遇点到环入口点，于是在链表头与相遇点分别设置一个指针，每一次各走一步，两个指针必定相遇，且遇到的第一个点为环入口点。 具体代码如下：

/** * 寻找循环链表的环入口 * @return */ public Node findLoopPort(Node head){ Node slow = head; Node fast = 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; }

9.在不知道头结点情况下删除指定节点

如果为链表尾节点，则不能删除，因为不能设置前驱节点的next指针置为空可以交换节点与后续节点的值，然后删除后续节点。 具体代码如下： /** * 不知道头结点的情况下，删除指定节点 * @param n * @return */ public boolean deleteNode(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; return true; }

10.判断两个链表是否相交及找出第一个相交点

如果两个链表相交，那么他们的尾结点一定相同

/** * 判断两个链表是否相交 * @param h1 * @param h2 * @return */ public boolean isIntersect(Node h1,Node h2){ if (h1==null || h2==null){ return false; } Node tail1 =h1; while (tail1!=null){ tail1 = tail1.next; } Node tail2 = h2; while (tail2!=null){ tail2 = tail2.next; } return tail1==tail2; }

如何找出第一个相交的点？ 首先分别计算两个链表的长度。长的链表先遍历（len1 - len2）步，使剩下的长度相等，然后两个链表一起遍历。每一步都比较值是否相等。如果相等，就返回节点。

public static Node getFirstMeetNode(Node h1,Node h2){ if (h1==null||h2==null){ return null; } Node tail1 = h1; int len1=1; while (tail1!=null){ tail1=tail1.next; len1++; } Node tail2 = h2; int len2=1; while (tail2.next!=null){ tail2=tail2.next; len2++; } //两链表不相交 if (tail1!=tail2){ return null; } Node t1 = h1; Node t2 = h2; //找出较长的链表，先遍历 if (len1>len2){ int d =len1-len2; while (d!=0){ t1 = t1.next; d--; } }else { int d =len2 - len1; while (d!=0){ t2 = t2.next; d--; } } while (t1!=t2){ t1=t1.next; t2=t2.next; } return t1; }