单链表问题（反转、是否有环、删除结尾第N个节点、合并两个sortlist、找到交点）

1.时间复杂度O(N),内存O(1)的效率下实现单链表的翻转

public static TreeNode revers(TreeNode head){TreeNode temp,first,second;first=head;second=head.next;while(second!=null){temp=second.next;second.next=first;first=second;second=temp;}head.next=null;head=first;return head;}

2.判断一个链表是否存在环，采用的方法是一个指针按照补偿为1遍历，另一个按照步长为2遍历，如果重合说明有环。

public class IfHasCircle {public static boolean ifhascircle(TreeNode head){TreeNode first=head;TreeNode second=head;while(first!=null && second!=null){if(first==second){return true;}first=first.next;second=second.next.next;}return false;}

3.删除从结尾处数第n个节点。思路是做两个指针，一个步长比另一个长n，这样当长的那个节点遍历到最后一个的时候，就直接把短的节点删除即可。

public static TreeNode DelTheLastN(TreeNode head,int n){TreeNode first,second;first=head;second=head;for(int i=1;i<=n;i++){second=second.next;}while(second.next!=null){second=second.next;first=first.next;}first.next=first.next.next;return head;}

4.合并两个sort list：用递归

static TreeNode mergTwoSortList(TreeNode l1,TreeNode l2){if(l1 == null) return l2;if(l2 == null) return l1;if(l1.val < l2.val) {l1.next = mergTwoSortList(l1.next, l2);return l1;} else {l2.next = mergTwoSortList(l2.next, l1);return l2;}}

5. 两个链表相交，找出交点

求出两个链表的长度a和b，一个指针指向较短链表的头head，另一个指针指向较长链表的第head+|a-b|，然后两个指针一起移动，相遇处即为交点。

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) {* val = x;* next = null;* }* }*/ public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headA==null || headB==null) return null;int Aindex_length=getLength(headA);int Bindex_length=getLength(headB);int dis=Math.abs(Aindex_length-Bindex_length);ListNode Aindex=headA;ListNode Bindex=headB;if(Aindex_length>=Bindex_length){for(int i=0;i<dis;i++){Aindex=Aindex.next;} while(Bindex!=null){if(Aindex.val==Bindex.val){return Aindex;}else{Aindex=Aindex.next;Bindex=Bindex.next;}}}Aindex=headA;Bindex=headB;if(Aindex_length<Bindex_length){for(int i=0;i<dis;i++){Bindex=Bindex.next;} while(Aindex!=null){if(Aindex.val==Bindex.val){return Aindex;}else{Aindex=Aindex.next;Bindex=Bindex.next;}}}return null;}public int getLength(ListNode head){ListNode index=head;int length=1;while(index.next!=null){index=index.next;length++;}return length;} }

/********************************

* 本文来自博客  “李博Garvin“

* 转载请标明出处:http://blog.csdn.net/buptgshengod

******************************************/

总结

以上是生活随笔为你收集整理的单链表问题（反转、是否有环、删除结尾第N个节点、合并两个sortlist、找到交点）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。