24. 两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
输入：head = [1,2,3,4]
输出：[2,1,4,3]
这题很简单就不写思路了
public ListNode swapPairs(ListNode head) {
ListNode dummyNode = new ListNode();
dummyNode.next = head;
ListNode tmp = dummyNode;
while(tmp.next!=null&&tmp.next.next!=null){
ListNode next1 = tmp.next;
ListNode next2 = tmp.next.next;
tmp.next = next2;
next1.next = next2.next;
next2.next = next1;
tmp = next1;
}
return dummyNode.next;
}
19.删除链表的倒数第N个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
思路 : 先把链表的长度size遍历出来,然后找到size-n位置的节点,把这个节点删除掉.为了把size-n位置的节点内容删掉,我只能在开头构建一个虚拟节点,这样的话size-n找到的位置就是要删除节点的前一个节点,这样方便我做指针变化的删除操作.综合来说,此题也是简单题.
代码如下:
public ListNode removeNthFromEnd(ListNode head, int n) {
int size = getSize(head);
int index = size - n;
ListNode dummyNode = new ListNode(0,head);
ListNode tmp = dummyNode;
int i = 0;
while(i!=index){
tmp = tmp.next;
i++;
}
tmp.next = tmp.next.next;
return dummyNode.next;
}
public int getSize(ListNode head){
int size = 0;
while(head!=null){
size++;
head = head.next;
}
return size;
}
面试题 02.07. 链表相交
此题目前认为官方题解有问题,还在研究中,暂不讨论
142.环形链表II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
其实这道题用HashSet写挺简单的,HashSet全是优点,使用了数组+Hashcode+链表+红黑树,追求极致性能,是基于数组的实现.
ListNode index = head;
Set<ListNode> visited = new HashSet<ListNode>();
while(index!=null){
if(visited.contains(index)){
return index;
}else{
visited.add(index);
}
index = index.next;
}
return null;