Java单链表接本操作

Java单链表基本操作： （一）顺序查找； （二）指定位置增加节点； （三）删除当前节点； （四）单链表反转； （五）输出倒数第K个节点； （六）删除重复节点； （七）排序 （八）合并两个排序单链表； （九）交换相邻节点的值； （十）O（n）时间内查找单链表的中间节点 （十一）逆序（从尾至头）输出单链表 （十二）判断单链表是否有环 （十三）判断两个链表是否相交 （十四）已知一个单链表中存在环，求进入环中的第一个节

定义node：

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

定义ListNode：

public class ListNode { public static Node getSingleList(){ Node head=new Node(3); Node node1=new Node(6); Node node2=new Node(8); Node node3=new Node(6); Node node4=new Node(2); head.next=node1; node1.next=node2; node2.next=node3; node3.next=node4; node4.next=null; return head; } public static void printList(Node node){ System.out.print("List:"); while(node!=null){ System.out.print(node.data+"-->"); node=node.next; } System.out.println(); } }

（一）顺序查找

/* * 查找值为num的元素位置，没有返回-1*/ public class SeqSearch { public static void main(String[] args) { Node head=ListNode.getSingleList(); ListNode.printList(head); int num=9; int id=new SeqSearch().searchNumId(head,num); System.out.println("要查找的元素位置为："+id); } public int searchNumId(Node head,int num){ int id=1; while(head!=null&&head.data!=num){ head=head.next; id++; } if(head==null) id=-1; return id; } }

（二）指定位置增加节点

/* * 将新节点增加在指定位置*/ public class AddNode { public static void main(String[] args) { Node head=ListNode.getSingleList(); ListNode.printList(head); Node add=new Node(0); int id=0; head=new AddNode().addNode(head,add,id); ListNode.printList(head); } public Node addNode(Node head,Node add,int id){ if(id==0) { add.next=head; head=add; }else{ while(head.next!=null&&id>1){//寻找节点增加的位置 head=head.next; id--; } add.next=head.next; head.next=add; } return head; } }

（三）删除当前节点

单链表中要删除当前节点，如果当前节点不是头节点，则无法使前面的节点直接指向后面的节点，这时候我们可以换一种思路，即：将当前节点的下一节点值附给当前节点，然后删除当前节点的下一节点，这样就等效为删除当前接节点了。

/** * Definition for singly-linked list. * public class Node { * int data; * Node next; * Node(int x) { data = x; } * } */ public void deleteNode(Node node) { node.val=node.next.val; node.next=node.next.next; }

（四）单链表反转

可以参考http://blog.csdn.net/u010305706/article/details/50810005 表示更详细

public class ReverseSingleList { public static void main(String args[]){ Node head=ListNode.getSingleList(); ListNode.printList(head); head=new ReverseSingleList().reverseSingleList(head); ListNode.printList(head); } public Node reverseSingleList(Node head){ if(head== null||head. next== null){ return head; } Node preNode=head; Node pNode=head. next; Node markNode=head. next; head. next= null; //一定要断开head节点的next节点，不然形成了循环 while(markNode!= null){ markNode=markNode. next; pNode. next= preNode; preNode=pNode; pNode=markNode; } return preNode; } }

（五）查找倒数第K个节点

package listnode; public class LastKNode { public static void main(String[] args) { Node head=ListNode.getSingleList(); ListNode.printList(head); int k=3; head=new LastKNode().getLastKNode(head,k); System.out.println(head.data); } public Node getLastKNode(Node head, int k){ Node node=head; while(node. next!= null&&k>0){ node=node. next; k--; } while(node!= null){ node=node. next; head=head. next; } return head; } }

（六）删除重复节点

package listnode; public class DeleteDuplecate_SingleList { public static void main(String[] args) { Node head=ListNode.getSingleList(); ListNode.printList(head); deleteNode(head); ListNode.printList(head); } public static void deleteNode(Node head){ while(head.next!=null){ Node p=head; while(p.next!=null){ if(p.next.data==head.data){ p.next=p.next.next; } p=p.next; } head=head.next; } } }

（七）排序

单链表的插入排序比数组麻烦，因为每次都都要从头节点开始往后遍历，头节点也需要单独处理

package listnode; public class SortList { public static void main(String[] args) { Node head=ListNode.getSingleList(); ListNode.printList(head); head=new SortList().insertSortList(head); ListNode.printList(head); } public Node insertSortList(Node head){ Node p=head.next; Node pre=head; while(p!=null){ Node cur=head; //比较节点，每次都是从头节点开始 Node q=p.next; if(p.data<head.data){ //由于是单链表，每次只能从头节点开始比较 pre.next=q; p.next=head; head=p; }else while(cur.next!=p){ if(p.data<cur.next.data){//将P与cur.next进行比较，方便单链表插入 pre.next=q; p.next=cur.next; cur.next=p; p=pre; //保证pre每次指向的都是p前面的一个节点 }else cur=cur.next; } pre=p; p=q; } return head; } }

（八）合并两个有序单链表

package listnode; public class MergeSeqList { public static void main(String[] args) { Node head1=SortList.insertSortList(ListNode.getSingleList()); Node head2=SortList.insertSortList(ListNode.getSingleList()); head1=new MergeSeqList().mergeTwoLists(head1, head2); ListNode.printList(head1); } public Node mergeTwoLists(Node l1, Node l2) { Node head=null; if(l1==null){//先判断两个链表是否为空 return l2; } if(l2==null){ return l1; } if(l1.data<=l2.data){ head=l1; l1=l1.next; }else{ head=l2; l2=l2.next; } Node temp=head; while(l1!=null&&l2!=null){ if(l1.data<=l2.data){ temp.next=l1; l1=l1.next; }else{ temp.next=l2; l2=l2.next; } temp=temp.next; } if(l1!=null){ temp.next=l1; } if(l2!=null){ temp.next=l2; } return head; } }

（九）交换相邻节点对的值

本题目来源于：Leetcode: 24.swap nodes in pairs(单链表中交换节点对的值) Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should return the list as 2->1->4->3. Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed. 有两种思路解决本题： （1）利用链表的特点，改变链表指针的指向，改变了节点的位置

package listnode; public class SwapPairs { public static void main(String[] args) { Node head=ListNode.getSingleList(); ListNode.printList(head); head=new SwapPairs().swapPairs(head); ListNode.printList(head); } public Node swapPairs(Node head) { Node root=head; if(head!=null&&head.next!=null){ root=head.next; Node pre=head; Node p=null; Node q=null; while(head!=null&&head.next!=null){ p=head.next; q=p.next; pre.next=p; p.next=head; head.next=q; pre=head; head=q; } } return root; } }

（2）改变相邻节点对的值，不改变节点指针（通过数组思维实现）

public ListNode swapPairs(ListNode head){ public ListNode swapPairs(ListNode head) { ListNode p=head; while(p!=null){ ListNode q=p.next; if(q!=null){ int temp=p.val; p.val=q.val; q.val=temp; p=p.next; } p=p.next; } return head; } }

（十）判断是否有环并输出环长度以及环的入口节点

本文解决三个问题：

1.单链表是否有环？ 2.有则输出环的长度？ 3.找到环的入口节点？

分析： 定义两个指针fast 和slow，fast每次向后移动两个节点，slow每次想后移动一个节点。 1.如果没有环，则fast首先到达链表结尾； 2.链表有环的情况下：fast与slow两次相遇，slow中间走过的节点处即为环的长度； 3.找环的入口节点稍微复杂点，有如下的推导过程：

相遇的时候，slow共移动了s步，fast共移动了2s步。 定义a如下： 链表头移动a步到达入口点。 定义x如下： 入口点移动x步到达相遇点。 定义r如下： 环的长度。 定义L如下： 链表总长度为L。

其中Ｌ　＝　a + r

那么slow和fast相遇了，fast必然比slow多走了n个圈，也就是 n*r 步，那么 s = a + x 2s = s + n*r ， 可得 s = n*r 将s=a+x，带入s =n*r，可得 a+x = n*r, 也就是 a+x = (n-1)*r + r 　　 从表头移动到入口点，再从入口点移动到相遇点，也就是移动了整个链表的距离，即是 L = a + r , 所以r = L - a 所以 a+x = (n-1)*r + L - a , 于是 a = (n-1)*r + L - a - x 得到：从表头到入口点的距离，等于从相遇点到入口点的距离。 所以，从表头设立一个指针，从相遇点设立一个指针，两个同时移动，必然能够在入口点相遇，这样，就求出了相遇点。

上面三个问题的java解决代码：

方法一：一次性求解

public class ExistCircle { static int id = 1; public Node existCircle(Node head){ Node fast = head; Node slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; //输出环长 while(fast == slow) { int len = 1; fast = fast.next.next; slow = slow.next; while (fast != slow) { len++; fast = fast.next.next; slow = slow.next; } System.out.println("The length of circle is:" + len); //输出环入口节点 fast = head; while (fast != slow) { fast = fast.next; slow = slow.next; id++; } return slow; } } return null; } public static void main(String[] args) { Node head=new Node(3); Node node1=new Node(6); Node node2=new Node(8); Node node3=new Node(5); Node node4=new Node(2); Node node5=new Node(7); head.next=node1; node1.next=node2; node2.next=node3; node3.next=node4; node4.next=node5; node5.next=node3; Node port = new ExistCircle().existCircle(head); System.out.println("环入口为第" + id + "个节点:" + port.data); } }

方法二:分开求解：

package listnode; public class ExitCircle { static int id = 1; public static void main(String[] args) { //测试 Node head=new Node(3); Node node1=new Node(6); Node node2=new Node(8); Node node3=new Node(5); Node node4=new Node(2); Node node5=new Node(7); head.next=node1; node1.next=node2; node2.next=node3; node3.next=node4; node4.next=node5; node5.next=node3; new ExitCircle().exitCircle(head); Node port = new ExitCircle().findLoopPort(head); System.out.println("环入口为第" + id + "个节点:" + port.data); } //环入口节点 //环的入口节点到快慢指针相遇的距离 与 链表头节点到环入口节点的距离相等 public Node findLoopPort(Node head){ Node slow = head, fast = head; while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; if(slow == fast){ fast = head; while(head != slow){ id++; head = head.next; slow = slow.next; } return slow; } } System.out.print("NoLoop !"); return null; } public boolean exitCircle(Node head){ Node fast = head; Node slow = head; while(fast != null && fast.next != null){//判断是否由环，注意fast.next = null的情况 fast = fast.next.next; slow = slow.next; if(fast == slow){//存在环 int count = 0; while(true){ count ++; fast = fast.next.next; slow = slow.next; if(fast == slow){//快慢指针在第二次相遇，这个点肯定是第一次相遇的点 System.out.println("环的长度：" + count); return true; } } } } System.out.println("false!"); return false; } }