数据结构：链表相关题目

链表反转

LeetCode地址：LCR 024. 反转链表 - 力扣（LeetCode）

头插法：

class Solution {public ListNode reverseList(ListNode head) {ListNode h1 = new ListNode(-1);while(head!=null){ListNode index = new ListNode(head.val);index.next = h1.next;h1.next = index;head = head.next;}return h1.next;}
}

判断链表是否成环

LeetCode地址：141. 环形链表 - 力扣（LeetCode）

快慢指针：快指针追慢指针，相遇即为有环，如果走到null即为无环。

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

判断链表成环的位置

LeetCode地址：LCR 022. 环形链表 II - 力扣（LeetCode）

判断环的过程和上一题一致，相遇让两个指针的其中一个从head开始与另一个指针一起每次走一步，再次相遇时的位置即为成环的位置。

证明过程：

 

设head到入口的距离为a

入口到相遇点的距离为b

相遇点到入口的距离为c

且p2到相遇时走了n圈环,p1走了m圈

p1的路程为 a+b+m*k

p2的路程为a+b+n*k

2*((a+b)+m*k)=a+b+n*k

a=(n-2m)*k-b
a=(n-2m-1)*k+c

public class Solution {public ListNode detectCycle(ListNode head) {if(head==null||head.next==null){return null;}ListNode p1 = head;ListNode p2 = head;while(p2.next!=null&&p2.next.next!=null){p1 = p1.next;p2 = p2.next.next;if(p1==p2){p1 = head;while(p1!=p2){p1 = p1.next;p2 = p2.next;}return p1;}}return null;}
}

合并两个有序链表

LeetCode地址：LCR 022. 环形链表 II - 力扣（LeetCode）

比较两个链表的值，将小的使用尾插法插到要返回的链表上，当一个链表为空时，直接将另一个链表剩下的直接插入要返回的链表。

class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode res = new ListNode(-1);ListNode tail = res;while(list1!=null&&list2!=null){if(list1.val<list2.val){tail.next=new ListNode(list1.val);list1 = list1.next; }else{tail.next=new ListNode(list2.val);list2 = list2.next; }tail = tail.next;}if(list1!=null){tail.next = list1;}else{tail.next = list2;}return res.next;}
}