代码随想录训练营 Day04- 链表下
作者：jjn0703
- 2023-07-02 江苏
本文字数：1473 字
阅读完需：约 5 分钟
作业题
24. 两两交换链表中的节点
public class LeetCode24 { public ListNode swapPairs(ListNode head) { ListNode pre = new ListNode(0); pre.next = head; ListNode temp = pre; while(temp.next != null && temp.next.next != null) { ListNode start = temp.next; ListNode end = temp.next.next; temp.next = end; start.next = end.next; end.next = start; temp = start; } return pre.next; }}
复制代码
19. 删除链表的倒数第 N 个结点
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode fast = dummy, slow = dummy; int i = 0; for (; i <= n && fast != null; i++) { fast = fast.next; } while (fast != null) { fast = fast.next; slow = slow.next; } if (slow != null && slow.next != null) { slow.next = slow.next.next; } return dummy.next; }}复制代码
面试题 02.07. 链表相交
/** * 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) { ListNode first = headA, second = headB; while (first != second) { first = (first !=null) ? first.next : headB; second = (second != null) ? second.next : headA; } return first; }}复制代码
142. 环形链表 II
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public ListNode detectCycle(ListNode head) { // 初始化的时候,均指向头结点 ListNode fast = head, slow = head; while (true) { // 快指针碰到null,说明不存在环 if (fast == null || fast.next == null) { return null; } fast = fast.next.next; slow = slow.next; if (fast == slow) { break; } } // 重新让快指针回到头结点,快慢指针再次相遇时，其距离一定等于a + n * b fast = head; while (fast != slow) { fast = fast.next; slow = slow.next; } return fast; }}复制代码
总结
for 循环的结束条件可以通过临界值带入来判断代码写的是否正确；
求倒数第 N 个节点，可以转化为快慢指针，快指针先走 N 步，慢指针再出发，快指针走到尾部，慢指针所在位置即是要求的节点。
划线
评论
复制
发布于: 刚刚阅读数: 4
版权声明: 本文为 InfoQ 作者【jjn0703】的原创文章。
原文链接:【http://xie.infoq.cn/article/97e14e5e6bca1d9f6ff8a44dc】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
jjn0703
关注
Java工程师/终身学习者 2018-03-26 加入
USTC硕士/健身健美爱好者/Java工程师.
评论