反转链表

206. 反转链表 - 力扣（LeetCode）

思路解透

本题就是通过不停地将最先的 head 节点位置的后一位插到最前面，完成链表的反转
本题需要两个节点变量

1. cur：其任务就是定位到原 head 节点位置的前一位，然后将自己插入到当前 head 节点的前面
   • 因为链表的最后一个节点都是指向一个 null 值，所以需要将最先的 head 节点的 next 置为空
   • 但在将 head.next 置为 null 之前，需要先将 cur 节点实例化出来，不然 cur 就无法找到原先的 head 节点的位置了
2. curN：其任务就是定位到 cur 的后一个节点，方便让 cur 进行循环插入
   • 其在循环中进行实例化，因为每一次插入完成之后，curN 的位置都是需要随着 cur 的改变而改变
   • curN 实例化为 cur 的下一个节点。在 cur 插入完成后，cur 就会定位到 curN 的位置，若此为止不为 null，则继续进行前插

代码解析

class Solution {public ListNode reverseList(ListNode head) {//1. 防止空指针异常  if(head == null){  return head;  	}  //2. 将head.next置为空  //注意先把 cur 节点给先弄出来  ListNode cur = head.next;  head.next = null;  //3. 进行循环头插  while (cur != null) {  ListNode curN = cur.next;  cur.next = head;  head = cur;  cur = curN;  }  return head;}
}

---

寻找中间节点

876. 链表的中间结点 - 力扣（LeetCode）

思路解透

解法 1：定义一个 cur 节点，从 head 节点的地方，向后走 size()/2 步，就到了中间位置
解法 2：定义一个 slow 节点，一次走一步，在定义一个 fast 节点，一次走两步，当 fast 走完的时候，slow 就刚好在中间位置（快慢指针）

• 当有偶数个节点时，循环判断条件为：fast != null
• 当有奇数个节点时，循环判断条件为：fast.next != null
• 这里的两个条件判断顺序不能换，否则会报空指针异常错误

快慢指针原理：
路程一样的情况下，速度是两倍，那么当走完的时候，路程也是两倍

代码解析（法 1）

public ListNode middleNode(){  int count = 0;  ListNode node = head;  while(node != null){  count++;  node = node.next;  }    ListNode cur = head;  for (int i = 0; i < count/2; i++) {  cur = cur.next;  }    return cur;  
}

---

代码解析（法 2）

public ListNode middleNode(){  ListNode slow = head;  ListNode fast = head;  while(fast != null && fast.next != null){  //slow走一步，fast走两步slow = slow.next;  fast = fast.next.next;  }    return slow;  
}

---

返回链表中倒数第 k 个节点

面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）

思路解透

1. 首先判断 k 是否合法，链表是否为为 null
   1. k <= 0，返回-1
   2. （下面的第二点看完再回来）因为如果 k 大于链表长度的话，当 fast 走 k - 1 步的时候就会走出链表，所以在 fast 走 k-1 步的过程中如果出现 fast == null，则返回 -1
2. 定义两个节点，fast 先走 k - 1 步，随后 fast 和 slow 一起走，当 fast 走到最后了，slow 所在的地方就是倒数第 k 个节点

代码解析

public int kthToLast(int k) {  //判断k是否合法，链表是否为nullif(k <= 0 || head == null) {  return -1;  }    ListNode fast = head;  ListNode slow = head;  int count = 0;  while (count != k - 1) {  //fast先向后走k-1步        fast = fast.next;  if(fast == null){//判断k是否合法return -1;  }count++;  }    while (fast.next != null){//两个节点一起向后走，直到fast走到最后一个  fast = fast.next;  slow = slow.next;  }    return slow.val;  
}

---

合并两个有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

思路解透

创建一个新的链表，为虚拟节点（傀儡节点），然后对需要合并的两个链表中的值进行比较，谁小谁就接在虚拟节点后面

1. 创建一个新的节点 newH，在这个链表上进行合并，再创建一个 tmp 节点，用来指向 newH 链表中的最后一个节点
2. 当 headA != null && headB != null 的时候，进行比较
   1. 若 headA. val < headB. val，则将 headA 这个节点接在 newH 后面，即接在 tmp 节点后面，最后 tmp 和 headB 节点均向后移一位
   2. 若 headA. val > headB. val，则将 headB 这个节点接在 newH 后面，即接在 tmp 节点后面，最后 tmp 和 headB 节点均向后移一位
3. 当 headA == null || headB == null 的时候，剩下的一个链表里面的节点直接接到 newH 后面就行了
4. 最后返回 newH. next，因为 newH 是一个虚拟节点，不存在于要合并的链表中，它只是一个引子

代码解析

public ListNode mergeTwoLists(ListNode headA, ListNode headB) {  ListNode newH = new ListNode(0);  ListNode tmp = newH;  while(headA != null && headB != null){  if(headA.val < headB.val){  //将headA接到newH上面，随后后移tmp.next = headA;  headA = headA.next;  tmp = tmp.next;  }else if{  //将headB接到newH上面，随后后移tmp.next = headB;  headB = headB.next;  tmp = tmp.next;  }    }    if(headA == null){  //headA空了，将headB直接接到newH后面tmp.next = headB;  }    //headB空了，将headA直接接到newH后面if (headB == null) {  tmp.next = headA;  }    return newH.next;  
}

---

分割链表

链表分割_牛客题霸_牛客网 (nowcoder.com)

思路解透

构建两个区间，一个里面接上小于 x 的节点，一个里面接上大于 x 的节点，最后将这两个区间连接起来

0. 若链表为空
1. 遍历链表
   • 创建一个 cur 节点，用来遍历链表
2. 把对应的节点放到指定区间
   1. 在小区间里
      1. 创建 bs（before start） 节点指向区间里面最前面的一个节点，创建 be（before end） 节点指向区间里面最后一个节点
      2. 在小区间里面插入第一个节点的时候，bs 和 be 都指向这个节点，随后 cur 向后移
      3. 之后插入的节点均为尾插，bs 位置不变，be 始终指向新插入的节点
   2. 在大区间里
      1. 创建 as（after start） 节点指向区间里面最前面的一个节点，创建 ae（after end） 节点指向区间里面最后一个节点
      2. 在小区间里面插入第一个节点的时候，as 和 ae 都指向这个节点，随后 cur 向后移
      3. 之后插入的节点均为尾插，as 位置不变，ae 始终指向新插入的节点
3. 把两个区间连接起来
   1. 将 be 节点和 as 节点连接起来，并且将 ae 节点的 next 置为 null，作为新链表的尾巴，并且返回 bs 节点
   2. 若所有节点全在小区间里，就将 be 节点的 next 置为 null，作为新链表的尾巴，并且返回 bs 节点
   3. 若全在大区间里，则返回 ae 节点

代码解析

public ListNode partition(ListNode pHead, int x) {  //判断空链表if(pHead == null){  return null;  }      //小区间的两个节点ListNode bs = null;  ListNode be = null;  //大区间的两个节点ListNode as = null;  ListNode ae = null;  //遍历链表的节点ListNode cur = pHead;  while(cur != null){  //插入小区间if(cur.val < x){  //第一次插入if(bs == null){  bs = be = cur;  }else{  be.next = cur;  be = be.next;  } //插入大区间       }else{  //第一次插入if(as == null){  as = ae = cur;  }else{  ae.next = cur;  ae = ae.next;  }        }        cur = cur.next;  }    //当节点全部都在小区间时，直接返回大区间if(bs == null){  return as;  }    //进行大小区间的拼接be.next = as;  //大区间不为空，把最后一个节点置空，作为尾巴if(as != null){  ae.next = null;  }  return bs;  
}

---

回文链表

链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

思路解透

1. 首先用快慢指针找到中间的节点（上面第二题有讲解）
2. 再对后半部分进行反转（上面第一题有讲解）
3. 最后让首尾两个节点往中间走，直到相遇，返回 true；若是偶数个节点，则只需要前面节点的 next 与后面节点的值相等即可返回 true

代码解析

public boolean chkPalindrome(ListNode head) {  // write code here  if (head == null) {  return true;  }  //1. 找到链表的中间节点  ListNode fast = head;  ListNode slow = head;  while (fast != null && fast.next != null) {  slow = slow.next;  fast = fast.next.next;  }  //2. 反转后半节点  ListNode cur = slow.next;  slow.next = null;  while (cur != null) {  ListNode curN = cur.next;  cur.next = slow;  slow = cur;  cur = curN;  }  //3. slow从后往前，head从前往后，直到相遇  while (head != slow) {  if (head.val != slow.val) {  return false;  }        //当节点个数为偶数if (head.next == slow)  return true;  head = head.next;  slow = slow.next;  }    return true;  
}

---

相交链表

160. 相交链表 - 力扣（LeetCode）

思路解透

1. 首先计算两个链表的长度，并计算他们的差值
2. 随后让长的链表的头节点先走“差值“步，让他们站在同一起跑线
3. 最后让他们携手同行，直到相遇，返回任意一个链表；若最终零个引用都为空，证明不相交，返回 null

代码解析

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {  //1. 计算两个链表的长度，并计算差值  int lenA = 0;  int lenB = 0;  ListNode curA = headA;  ListNode curB = headB;  while (curA != null) {  curA = curA.next;  lenA++;  }    while (curB != null) {  curB = curB.next;  lenB++;  }    int len = lenA - lenB;  curA = headA;  curB = headB;  //2. 根据差值，长的链表头节点先走len步，  // 让两个链表在同一起跑线  if (len > 0) {  int count = 0;  while (count != len) {  curA = curA.next;  count++;  }    } else {  int count = 0;  while (count != -len) {  curB = curB.next;  count++;  }    }  //3. 两个链表的节点携手同行，直到相等  while (curA != curB) {  curA = curA.next;  curB = curB.next;  }    if (curA == null) {  //若两个引用都为空，证明不相交  return null;  }    return curA;  
}

---

环形链表

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

思路解透

1. 定义两个节点，一个一次走一步，一个一次走两步
2. 当走得快的节点不为空，并且走得快的节点的 next 不为空，循环就一直继续
3. 当两个节点相等，则返回 true

假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况
因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

代码解析

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

---

环形链表Ⅱ

142. 环形链表 II - 力扣（LeetCode）

思路解透

代码解析

public ListNode detectCycle(ListNode head) {  //1. 判断是否有环  ListNode fast = head;  ListNode slow = head;  while (fast != null && fast.next != null) {  fast = fast.next.next;  slow = slow.next;  //有环，跳出循环  if (fast == slow) {  break;  }    }    //若是因为没有环而跳出循环的话，返回null  if (fast == null || fast.next == null) {  return null;  }    //此时slow在相遇点，将fast拿到起始点  //让他们相向而行，相遇点即为入口点  fast = head;  while(fast != slow) {  fast = fast.next;  slow = slow.next;  }    return fast;  
}