hot100之链表上
<h3 id="相交链表160">相交链表(160)</h3><p>先看代码</p>
<pre><code class="language-java">public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p = headA;
ListNode q = headB;
while (p != q){
p = p != null ? p.next : headB;
q = q != null ? q.next : headA;
}
return p;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>将A的尾节点与B相连, B的尾节点与A相连</p>
<p><img src="https://img2024.cnblogs.com/blog/3642195/202506/3642195-20250610130155450-1353155162.png"></p>
<p>据图可知当(p, q)→(A, B指针)步频一致时, 会共同到达共有链表的初节点</p>
<h3 id="反转链表206">反转链表(206)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null){
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>通过先置哨兵节点, 避免节点数量过少导致<code>null pointer exception</code></p>
<h3 id="回文链表234">回文链表(234)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null){
fast = fast.next;
slow = slow.next;
if (fast.next != null){
fast = fast.next;
}
}
ListNode rig = reverse(slow);
ListNode lef = head;
while (rig != null){
if (rig.val != lef.val){
return false;
}
rig = rig.next;
lef = lef.next;
}
return true;
}
private ListNode reverse(ListNode node){
ListNode prev = null;
while (node != null){
ListNode next = node.next;
node.next = prev;
prev = node;
node = next;
}
return prev;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>通过快慢指针找到中心节点,反转中心节点后链表,取(lef, rig)→(链表头尾节点) 进行回文分析</p>
<h3 id="环形链表141">环形链表(141)</h3>
<p>先看代码</p>
<pre><code class="language-java">public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null){
fast = fast.next;
slow = slow.next;
if (fast != null){
fast = fast.next;
}else return false;
if (fast == slow) return true;
}
return false;
}
}
</code></pre>
<ul>
<li>通过快慢指针, 快指针相对慢指针移动速度为1, 若有环, 必然追上慢指针</li>
</ul>
<h3 id="环形链表ii142">环形链表II(142)</h3>
<p>先看代码</p>
<pre><code class="language-java">public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
if (fast == null || fast.next == null) {
return null;
}
slow = head;
while (slow != fast){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>当快慢指针相遇时, 将慢指针置于head, 同步快慢指针步频, 再次相遇即为入口处</p>
<blockquote>
<p>证明<br>
f,s 为快慢指针移动的步数<br>
a, b分别为为环外长度, 环内长度<br>
由 f = 2s, f = s + n∗b<br>
有 f = 2n∗b, s = n∗b<br>
因 f + a = 2n∗b + a 此时快指针指向环形链表入口<br>
取p = head, 有 (p+a)%(n∗b) == (f+a)%(n∗b) == a<br>
p 和 f在入口相遇</p>
</blockquote>
<h3 id="合并两个有序链表021">合并两个有序链表(021)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode p1 =list1;
ListNode p2 =list2;
ListNode dummy = new ListNode(-1) ;
ListNode res = dummy;
while(p1!= null && p2!=null){
if ( p1.val <= p2.val){
dummy.next =p1;
p1 = p1.next;
}else {
dummy.next = p2;
p2 = p2.next;
}
dummy =dummy.next;
}
if (p2 != null){
dummy.next = p2;
dummy= dummy.next;
}
if (p1!= null){
dummy.next = p1;
dummy = dummy.next;
}
return res.next;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>通过先置prev哨兵节点, 避免节点数量过少导致<code>null pointer exception</code></p>
<h3 id="两数相加002">两数相加(002)</h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0){
if (l1 != null){
carry += l1.val;
l1 = l1.next;
}
if (l2 != null){
carry += l2.val;
l2 =l2.next;
}
p = p.next = new ListNode(carry%10);
carry /= 10;
}
return dummy.next;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>carry记录两数相加,并作为传参, 传递给下一循环</p>
<h3 id="删除链表的倒数第-n-个结点019"><strong>删除链表的倒数第 N 个结点(019)</strong></h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1, head);
ListNode sentry = dummy;
ListNode cur = dummy;
for (int i = 0; i < n +1; i++) {
sentry =sentry.next;
}
while (sentry != null){
sentry =sentry.next;
cur = cur.next;
}
cur.next = cur.next.next;
return dummy.next;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>保持n作为节点相对距离</p>
<p>让sentry先走n步, 当 sentry走到末尾, cur也到了要删除的节点处</p>
<h3 id="两两交换链表中的节点024"><strong>两两交换链表中的节点(024)</strong></h3>
<p>先看代码</p>
<pre><code class="language-java">class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null){
return head;
}
ListNode next = head.next;
head.next = swapPairs(next.next);
next.next = head;
return next;
}
}
</code></pre>
<ul>
<li>感悟</li>
</ul>
<p>递归的代码就是简洁</p><br><br>
来源：https://www.cnblogs.com/many-bucket/p/18921995
頁:
[1]