绍兴柯桥建设局网站百度站长提交
本文以收录专题刷题记录
目录
24. 两两交换链表中的节点
题目链接
思路
代码
19. 删除链表的倒数第 N 个结点
题目链接
思路-双指针
代码
面试题 02.07. 链表相交
题目链接
思路
代码
24. 两两交换链表中的节点
题目链接
力扣
思路
建议使用虚拟节点,这样每次对头结点操作就不需要单独处理了
接下来就是简单的模拟过程
一定要画图 不然指针指来指去容易乱
代码
class Solution {public ListNode swapPairs(ListNode head) {ListNode node = new ListNode(0);node.next = head;ListNode cur = node;while (cur.next != null && cur.next.next != null){ListNode temp = cur.next.next;cur.next = head.next;head.next = temp.next;temp.next = head;cur = head;head = cur.next;}return node.next;}
}
19. 删除链表的倒数第 N 个结点
题目链接
力扣
思路-双指针
在这里我们尝试进阶写法,只使用一次遍历得到结果。
首先使用虚拟头结点,这样方便处理删除实际头结点的逻辑。
定义fast指针和slow指针,初始值为虚拟头结点,fast首先走n + 1步 ,为什么是n+1呢,因为只有这样同时移动的时候slow才能指向删除节点的上一个节点(方便做删除操作)。
fast和slow同时移动,直到fast指向末尾,删除slow指向的下一个节点
代码
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummyhead = new ListNode(-1);dummyhead.next = head;ListNode fast = dummyhead;ListNode slow = dummyhead;while (n -- > 0){fast = fast.next;}while (fast.next != null){fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummyhead.next;}
}
面试题 02.07. 链表相交
题目链接
力扣
思路
注意交点不是数值相等,而是指针相等。
我们求出两个链表的长度,并求出两个链表长度的差值,然后让curA移动到,和curB 末尾对齐的位置,此时我们就可以比较curA和curB是否相同,如果不相同,同时向后移动curA和curB,如果遇到curA == curB,则找到交点。否则循环退出返回空指针。
代码
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode curA = headA;ListNode curB = headB;int lenA = 0,lenB = 0;while (curA != null){lenA ++;curA = curA.next;}while (curB != null){lenB ++;curB = curB.next;}if (lenA > lenB){lenA = lenA - lenB;lenB = 0;}else {lenB = lenB - lenA;lenA = 0;}curA = headA;curB = headB;while (lenA-- > 0){curA = curA.next;}while (lenB -- > 0){curB = curB.next;}while (curA != null){if (curA == curB){return curA;}curA = curA.next;curB = curB.next;}return null;}
}