LeetCode 24. 两两交换链表中的节点
题目链接：两两交换链表中的节点题目链接
思路
这道题其实就是一个模拟题，要求每次交换链表中两个相邻的节点（1、2 节点互换；3、4 节点互换；2、3 节点不互换，意思就是交换过的节点不参与后续的交换了），同时只能进行节点交换，不能进行值交换。主要考察的就是指针变换的先后顺序。为了确保链表中的头指针和其他指针的操作模式相同，所以添加了虚拟头节点。所以每次 cur 先指向需要交换的两个节点的前一个节点，将这三个节点记作 0、1、2。那么具体的指向过程就是 0 先指向 2，1 指向 2 的后一个节点，2 指向 1，即完成了交换过程。
代码
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyhead=new ListNode(0);
dummyhead.next=head;
ListNode cur=dummyhead;
while(cur.next!=null&&cur.next.next!=null)
{
ListNode temp1=cur.next;
ListNode temp2=cur.next.next;
cur.next=temp2;
temp1.next=temp2.next;
temp2.next=temp1;
cur=cur.next.next;
}
return dummyhead.next;
}
}
时间复杂度：O (n) 遍历了整个链表
空间复杂度：O (1) 没有创建新的链表
LeetCode 19. 删除链表的倒数第 N 个节点
题目链接：删除链表的倒数第N个节点
思路
删除链表的倒数第 N 个节点需要我们将一个指针指向倒数第 N 个节点的前一个节点才可以完成删除第 N 个节点的操作。我们可以使用双指针的做法来解决本题，一个指针 fast 先向前走 N 次，然后再让 fast 和 slow 指针一起走，走到 fast.next!=null 为止，此时 slow 指针指向要删除的节点的前一个节点，此时我们执行删除操作就可以了。
代码
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyhead=new ListNode(0);
dummyhead.next=head;
ListNode fast=dummyhead;
ListNode slow=dummyhead;
for(int i=1;i<=n;i++)
fast=fast.next;
while(fast.next!=null)
{
fast=fast.next;
slow=slow.next;
}
slow.next=slow.next.next;
return dummyhead.next;
}
}
LeetCode面试题02.07.链表相交
题目链接：链表相交题目链接
思路
该题目给定两个单链表，让我们求两个单链表相交的起始节点。因为两个单链表相交后的那部分长度是相同的，但是未相交前的长度不一定相同，所以我们需要先求解两个单链表的长度，然后将两个单链表的长度缩减为相同长，然后再比较两个单链表是否有节点相同部分，如果有的话，一开始的节点相同部分就是两个单链表的相交部分。
代码
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA=headA;
ListNode curB=headB;
int lenA=0;
int lenB=0;
while(curA!=null)
{
curA=curA.next;
lenA++;
}
while(curB!=null)
{
curB=curB.next;
lenB++;
}
curA=headA;
curB=headB;
if(lenA>=lenB)
{
int gap=lenA-lenB;
while(gap-->0)
curA=curA.next;
while(curA!=null)
{
if(curA==curB)
return curA;
curA=curA.next;
curB=curB.next;
}
}
else
{
int gap=lenB-lenA;
while(gap-->0)
curB=curB.next;
while(curB !=null)
{
if(curB==curA)
return curB;
curB=curB.next;
curA=curA.next;
}
}
return null;
}
}
LeetCode142.环形链表Ⅱ
题目链接：环形链表Ⅱ题目链接
思路
首先我们设计一个快指针 fast，然后设计一个慢指针 slow，每次让 fast 走两步，让 slow 走一步，如果出现了 fast==slow ，那么说明链表中一定有环。那么为什么 fast 和 slow 一定可以相遇呢？因为 fast 和 slow 相遇，一定是 fast 又追上了 slow，那么相对于 slow 来说，fast 每次走一步，所以是不会跳过 slow 的，而是一定会遇到的。那么我们设头节点到环形链表的入口的距离为 x，环形链表的入口到 fast 和 slow 相遇的位置的距离为 y，fast 和 slow 相遇的位置到环形链表的入口的距离为 z。Fast 和 slow 相遇时，slow 走的距离为 x+y，fast 走的距离为 x+y+n (y+z)，因为 fast 走的距离是 slow 走的距离的两倍，所以等式 2 (x+y)=x+y+n (y+z) 成立，将等式优化一下，可以得到 x=(n-1)(y+z)+z，n 是一定大于等于 1 的，因为 fast 在追上 slow 时一定会已经走了一圈了。假设 n=1，可以得到 x=z。说明从头节点走到环形链表的入口和从相遇节点走到环形链表的入口的距离时相等的，如果 n>1，则说明从头节点走到环形链表的入口和从相遇节点走到环形链表的入口+在环里走的圈数的距离时相等的，那么当我们找到 fast 和 slow 相遇的地方时，我们只需要设计两个指针，一个指针从头节点开始走，每次走一步，一个指针从相遇节点开始走，每次走一步，当这两个节点相遇时，所在的位置就是环形链表的入口节点。
代码
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast=head;
ListNode slow=head;
while(fast!=null&&fast.next!=null)
{
slow=slow.next;
fast=fast.next.next;
if(slow==fast)
{
ListNode index1=slow;
ListNode index2=head;
while(index1!=index2)
{
index1=index1.next;
index2=index2.next;
}
return index1;
}
}
return null;
}
}