1. LeetCode 24. 两两交换链表中的节点
1.1 思路
- 定义虚拟头节点dummyhead，要不然每次针对头结点（没有前一个指针指向头结点），还要单独处理，并且cur=dummyhead，因为这里的步骤是首先cur下一个先指向节点2，然后节点2下一个指向节点1，再然后是节点1下一个指向节点3，最后让cur指向翻转后的节点1，直接cur=first就行。所以需要dummyhead的原因就是因为cur要指向要翻转的两个节点的前一个节点。
- 具体实现先定义dummyhead，并且让dummyhead的next指向head，cur指向dummyhead，这样指向才能让最开始操作头节点和第二个节点的翻转
- 遍历过程while(cur.next!=null&&cur.next.next!=null)，第一个条件是针对如果链表上是偶数个节点，那如果cur.next为空那就结束循环，第二个条件是针对如果链表上是奇数个节点，那如果cur.next.next为空那就结束循环，这里不理解可以画图理解一下，注意这里要用&&不能用||，因为如果用了||那如果是奇数个节点，cur.next就不为空那就进入循环里进行翻转了，但奇数个节点最后单独那个节点不用翻转，所以要用&&
- 翻转步骤：首先cur下一个先指向节点2，然后节点2下一个指向节点1，再然后是节点1下一个指向节点3，最后让cur指向翻转后的节点1，直接cur指向节点1就行（因为翻转的是两个节点，到下两个节点了，直接后移两位，也就是指向节点1就行）。这里问题在于如果直接用cur.next=cur.next.next;cur.next.next=cur.next的方式操作的话就找不到原来的指针了，因此要用first保存cur.next，second保存cur.next.next，temp作为节点3保存cur.next.next.next（这里节点3有可能是个空指针，但没关系的）。上面翻转的cur.next=second;second.next=first;first.next=temp;cur=first;
- return dummyhead.next就是新的链表
1.2 代码
class Solution { public ListNode swapPairs(ListNode head) { ListNode dumyhead = new ListNode(-1); // 设置一个虚拟头结点 dumyhead.next = head; // 将虚拟头结点指向head，这样方面后面做删除操作 ListNode cur = dumyhead; ListNode temp; // 临时节点，保存两个节点后面的节点 ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点 ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点 while (cur.next != null && cur.next.next != null) { temp = cur.next.next.next; firstnode = cur.next; secondnode = cur.next.next; cur.next = secondnode; // 步骤一 secondnode.next = firstnode; // 步骤二 firstnode.next = temp; // 步骤三 cur = firstnode; // cur移动，准备下一轮交换 } return dumyhead.next; } }
2. LeetCode19.删除链表的倒数第N个节点
2.1 思路
- 如何找到倒数第n个节点呢？定义虚拟头节点dummyhead，它的next指向head，好处依然是方便我们不需要判断要删除的节点是不是头节点，这样删除的操作比较统一
- 定义fast和slow指针都指向dummyhead，然后让fast指针先移动n+1步，然后fast和slow同时移动直到fast指向null，此时slow就指向要删除的节点的前一个节点了
2.2 代码
public ListNode removeNthFromEnd(ListNode head, int n){ ListNode dummyNode = new ListNode(0); dummyNode.next = head; ListNode fastIndex = dummyNode; ListNode slowIndex = dummyNode; //只要快慢指针相差 n 个结点即可 for (int i = 0; i < n ; i++){ fastIndex = fastIndex.next; } while (fastIndex.next != null){ fastIndex = fastIndex.next; slowIndex = slowIndex.next; } //此时 slowIndex 的位置就是待删除元素的前一个位置。 //具体情况可自己画一个链表长度为 3 的图来模拟代码来理解 slowIndex.next = slowIndex.next.next; return dummyNode.next; }
3. LeetCode 面试题 02.07. 链表相交
3.1 思路
- 让curLong指向headA，curShort指向headB，假设是这样
- 然后遍历求出两链表的长度，以及差值len，让长的先走差值len步
- 然后while(curLong!=curShort)一直遍历两个后移，直到相等，最后return 其中一个就可以
3.2 代码
/** * 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; } //1、分别求两个链表的长度 int len1=0; int len2=0; ListNode curLong=headA;//假设长的是链表A ListNode curShort=headB;//假设短的是链表B while(curLong!=null){ len1++; curLong=curLong.next; } while(curShort!=null){ len2++; curShort=curShort.next; } //2、求差值步的len int len=len1-len2; if(len<0){//差值为负，说明长的是B curLong=headB; curShort=headA; len=len2-len1; }else{//差值为正，说明长的就是A curLong=headA; curShort=headB; } //3、长链表先走len步，这是个差值步，走了之后再一起走 while(len>0){ curLong=curLong.next; len--; } //4、一起走，直到相遇 while(curLong!=curShort){ curLong=curLong.next; curShort=curShort.next; } return curLong;//return curShort也行 } }
4. LeetCode 142.环形链表II
4.1 思路
- 这题其实有两问，一问判断是否有环，一问是找到环的入口
- 判断是否有环：快慢指针，相遇说明有环。怎么想到呢？假设没环是一条直线，这时快慢指针不可能相遇，这时想为什么快慢指针就会相遇呢？就不会一直错过吗？快指针每次走两步，慢指针每次走一步，肯定是快指针先入环然后才是慢指针，然后入环后就相当于快指针在追慢指针，然后速度差为1，那么快指针就相对于慢指针移动来说每次就移动一个位置，就相当于在一个节点一个节点的在靠近慢指针，所以一定会在环里相遇
- 如何找环入口：假设起点到环的入口距离为x，环入口到相遇点的距离为y，相遇点到环入口的距离为z。在相遇点相遇慢指针走了x+y，快指针走了x+y+n(y+z)，因为快指针走了n(n>=1)圈，因为快指针速度是慢指针的2倍，因此等式2(x+y)=x+y+n(y+z)，解得x=n(y+z)-y，如果n=1，则x=z
4.2 代码
public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) {// 有环 ListNode index1 = fast; ListNode index2 = head; // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口 while (index1 != index2) { index1 = index1.next; index2 = index2.next; } return index1; } } return null; } }
