java链表常见简单面试算法题

1. 头插法、尾插法
   头插法：先待插入指向头结点的next，后头结点的next指向待插入。
   尾插法：借助尾指针，直接插入

 /*** 头插法* @param head* @return*/public static Node head_insert(Node head, int t){Node node=new Node(t);node.setNext(head.getNext());head.setNext(node);return head;}/*** 尾插法* @param head* @return*/public static Node tail_insert(Node head,int t){Node tail=head;Node target=new Node(t);while (tail.getNext()!=null){tail=tail.getNext();}tail.setNext(target);return head;}
}

2. 单链表翻转
   力扣：LCR 024. 反转链表
   将翻转前的链表记pre，翻转后的记next（也是head）。结点依次翻转。

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

3. 链表成环判断
   力扣：141. 环形链表
   定义两个指针slow、fast，slow走一步，fast走两步遍历链表。相遇就有环

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

4. 链表成环位置判断
   力扣：LCR 022. 环形链表 II
   
   （1）定义一个A指针（指向开始点A）、B指针（指向相遇点B）。以相同速度移动，相遇点就是环的入口。

public class Solution {public ListNode detectCycle(ListNode head) {Boolean result=false;ListNode slow=head;ListNode fast=head;while (slow!=null&&fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;if(slow==fast){result=true;break;}}if(result==false){return null;}slow=head;while (slow!=fast){slow=slow.next;fast=fast.next;}return slow;}
}

（2）为什么慢指针和快指针相遇时一定没走完一圈？
将环平铺展开，假设慢指针走完一圈了，快指针走两圈的距离。在下图中看出快指针已经超过了慢指针，中途一定有相遇的瞬间。

5. 链表成环长度判断
   在上一题找到环入口的前提下，再定义一个指针，绕一圈环并记数。
6. 有序链表的合并
   力扣：21. 合并两个有序链表
   定义一个pre指针，始终指向已经排好序的链表尾结点。定义一个虚拟节点作为pre的初始节点。
   依次遍历两个链表取出小的那个结点作为pre的下一个结点。

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode head=new ListNode(0);ListNode pre=head;while(list1!=null&&list2!=null){if(list1.val<list2.val){pre.next=list1;pre=list1;list1=list1.next;}else{pre.next=list2;pre=list2;list2=list2.next;}}if(list1==null){pre.next=list2;}else{pre.next=list1;}return head.next;}
}