一、LeetCode-160、相交链表
- 解题思路：对于两条相交链表来说，长链表减去短链表即为他们两个的差值，可以让短的走完从新指向长的链表的头部，当长的走完的时候，两条链表正好处于平行的状态，当节点相等的时候即使交点。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA==null||headB==null){
return null;
}
ListNode A=headA;
ListNode B=headB;
while(A!=B){
if(A==null){
A=headB;
}else{
A=A.next;
}
if(B==null){
B=headA;
}else{
B=B.next;
}
}
return A;
}
二、LeetCode-206、反转链表
1、双指针迭代
- 解题思路：我们可以申请两个指针，第一个指针叫 pre，最初是指向 null 的。第二个指针 cur 指向 head，然后不断遍历 cur。每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。
public ListNode reverseList(ListNode head) {
//申请节点，pre和 cur，pre指向null
ListNode pre = null;
ListNode cur = head;
ListNode tmp = null;
while(cur!=null) {
//记录当前节点的下一个节点
tmp = cur.next;
//然后将当前节点指向pre
cur.next = pre;
//pre和cur节点都前进一位
pre = cur;
cur = tmp;
}
return pre;
}
2、递归解法（骚操作！！）
- 解题思路：递归的两个条件：
- 终止条件是当前节点或者下一个节点==null
- 在函数内部，改变节点的指向，也就是 head 的下一个节点指向 head 递归函数那句 head.next.next = head
public ListNode reverseList(ListNode head) {
//递归终止条件是当前为空，或者下一个节点为空
if(head==null || head.next==null) {
return head;
}
//这里的cur就是最后一个节点
ListNode cur = reverseList(head.next);
//这里请配合动画演示理解
//如果链表是 1->2->3->4->5，那么此时的cur就是5
//而head是4，head的下一个是5，下下一个是空
//所以head.next.next 就是5->4
head.next.next = head;
//防止链表循环，需要将head.next设置为空
head.next = null;
//每层递归函数都返回cur，也就是最后一个节点
return cur;
}
三、LeetCode-21、合并两个有序链表
1、递归方法解题
- 解题思路：取出来一个数之后，剩下的仍然是这道题的一个问题，因此可以使用递归。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
else if (l2 == null) {
return l1;
}
else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
2、迭代方法解题
- 解题思路：首先，我们设定一个哨兵节点 "prehead" ，这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 prev 指针，我们需要做的是调整它的 next 指针。然后，我们重复以下过程，直到 l1 或者 l2 指向了 null ：如果 l1 当前位置的值小于等于 l2 ，我们就把 l1 的值接在 prev 节点的后面同时将 l1 指针往后移一个。否则，我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面，我们都把 prev 向后移一个元素。
- 在循环终止的时候， l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表。
- 问题：这个和一开始我自己想的是一样的，但是这段代码没有考虑存在空链表的情况，只考虑了都存在的情况
- 另外对于怎样存储头节点：这里的方法很好，可以先建一个已知数据的一个节点，最终返回该节点的next即使头节点
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// maintain an unchanging reference to node ahead of the return node.
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
// exactly one of l1 and l2 can be non-null at this point, so connect
// the non-null list to the end of the merged list.
prev.next = l1 == null ? l2 : l1;
return prehead.next;
四、LeetCode-26、删除排序数组中的重复项
1、双指针迭代
- 解题思路：我们可以申请两个指针，第一个指针叫i，最初是指向0的。第二个指针 j 指向 1，然后不断遍历数组。每次判断如果相等，那么i就不动，一直增长j，j肯定是比ida，遇到不等的时候将j的值赋值给i，最终返回i+1。
public int removeDuplicates(int[] nums) {
int i=0;
for(int j=1;j<nums.length;j++){
if(nums[i]!=nums[j]){
i++;
nums[i]=nums[j];
}
}
return i+1;
}
2、System.arraycopy()方法的使用
- 解题思路：在循环体中控制循环条件，因为移动了数组后面的值，因此i要减1，重新怕段i和 后一个值得关系，不然会错过一个数。
public int removeDuplicates(int[] nums) {
int len=nums.length;
for(int i=0;i<len-1;i++){
if(nums[i]==nums[i+1]){
System.arraycopy(nums,i+1,nums,i,len-i-1);
len--;
i--;
}
}
return len;
}
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/
