//思路一：
//先反转链表，在从头到尾打印
//从尾到头打印链表
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> res = new ArrayList<>();
//逆置该链表
ListNode head = reverse(listNode);
while(head!=null){
res.add(head.val);
head = head.next;
}
return res;
}
private ListNode reverse(ListNode listNode){
ListNode pre = null;
ListNode cur = listNode;
while(cur!=null){
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}//思路二：
//递归思路
//要逆序打印链表 1->2->3（3,2,1)，可以先逆序打印链表 2->3(3,2)，最后再打印第一个节点 1。
//链表 2->3 可以看成一个新的链表，要逆序打印该链表可以继续使用求解函数。
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> res = new ArrayList<>();
if (listNode == null){
return res;
}
if(listNode.next==null){
res.add(listNode.val);
return res;
}
ArrayList<Integer> next = printListFromTailToHead(listNode.next);
res.addAll(next);
res.add(listNode.val);
return res;
}public ListNode EntryNodeOfLoop(ListNode pHead) {
if(pHead==null || pHead.next==null){
return null;
}
ListNode fast = pHead;
ListNode slow = pHead;
while(fast!=null && slow!=null){
slow = slow.next;
fast = fast.next;
if(fast!=null){
fast=fast.next;
}
if(fast==slow){
break;
}
}
//TODO：如果此时 fast==null 或许 fast.next==null 说明是不存在环的
if(fast == null || fast.next == null){
return null;
}
slow = pHead;
while(slow!=fast){
slow=slow.next;
fast=fast.next;
}
return slow;
}public ListNode removeElements(ListNode head, int val) {
if(head==null){
return null;
}
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode pre = dummyHead;
ListNode cur = head;
while(cur!=null){
if(cur.val==val){
pre.next = cur.next; //删除 cur
}else{
pre = cur;
}
cur = cur.next;
}
return dummyHead.next;
}//思路：
//1->2->2->3
//删除重复元素后 1->3
//1->2->2
//删除重复元素后 1
public ListNode deleteDuplication(ListNode pHead) {
if(pHead==null || pHead.next==null){
return pHead;
}
//设置虚拟头结点
ListNode dummyHead = new ListNode(-1);
dummyHead.next = pHead;
ListNode pre = dummyHead;
ListNode cur = pHead;
//pHead 链表至少有 1 个节点，cur 不为 null
while(cur.next!=null){
if(cur.val!=cur.next.val){ //相邻元素的值不相同，但是还不能说明 cur 不是重复元素，需要进一步判断
if(pre.next==cur){ // cur 不是重复元素
pre = cur;
}else{ //是重复元素删除
pre.next = cur.next;
}
}
cur = cur.next;
}
if(pre.next!=cur){ //针对：1->2->2 这种情况
pre.next =null;
}
return dummyHead.next;
}public ListNode FindKthToTail(ListNode head, int k) {
if (head == null)
return null;
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode p = dummyHead;
ListNode q = dummyHead; //先走 k 步
for(int i=0;i<k;i++){
q=q.next;
if(q==null){ // 说明 k 大于链表长度，这直接返回 null
return null;
}
}
while(q!=null){
p = p.next;
q = q.next;
}
return p;
}//思路一：
//使用指针
public ListNode ReverseList(ListNode head) {
if(head==null || head.next==null){
return head;
}
ListNode pre=null;
ListNode cur=head;
while(cur!=null){
ListNode next = cur.next;
cur.next = pre;
pre=cur;
cur=next;
}
return pre;
}//思路二：
//使用递归
public ListNode ReverseList(ListNode head) {
if(head==null || head.next==null){
return head;
}
//tail 是 head.next 链表反转后的最后一个结点
ListNode tail = head.next;
//反转 head.next 链表
ListNode next = ReverseList(head.next);
head.next = null; //注意：十分重要：head.next 链表反转后，未反转的只有 head 一个结点
tail.next = head;
return next;
}//写法一：
//时间复杂度：O(n)
//空间复杂度：O(n)
public ListNode Merge(ListNode list1, ListNode list2) {
if(list1==null){
return list2;
}
if(list2==null){
return list1;
}
ListNode dummyHead = new ListNode(-1);
ListNode tail = dummyHead;
while(list1!=null && list2!=null){
if(list1.val < list2.val){
ListNode node = new ListNode(list1.val);
tail.next = node;
tail = node;
list1 = list1.next;
}else{
ListNode node = new ListNode(list2.val);
tail.next = node;
tail = node;
list2 = list2.next;
}
}
if(list1==null){
tail.next = list2;
}
if(list2==null){
tail.next=list1;
}
return dummyHead.next;
}//写法二：
//时间复杂度：O(n)
//空间复杂度：O(1)
public ListNode Merge(ListNode list1, ListNode list2) {
if(list1==null){
return list2;
}
if(list2==null){
return list1;
}
ListNode dummyHead = new ListNode(-1);
ListNode cur=dummyHead;
while(list1!=null && list2!=null){
if(list1.val<list2.val){
cur.next = list1;
list1 =list1.next;
}else{
cur.next=list2;
list2=list2.next;
}
cur=cur.next;
}
if(list1!=null){
cur.next=list1;
}
if(list2!=null){
cur.next=list2;
}
return dummyHead.next;
}private TreeNode pre=null; //始终指向当前节点的前一个节点（因为是双向链表）
private TreeNode head=null; //链表的头结点
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null){
return null;
}
if(pRootOfTree.left==null && pRootOfTree.right==null){
return pRootOfTree;
}
inOrder(pRootOfTree);
return head;
}
//对以 node 为根节点的搜索二叉树进行遍历
private void inOrder(TreeNode node){
if(node==null){
return;
}
inOrder(node.left);
//构建双向链表的过程
node.left=pre;
if(pre!=null){
pre.right=node;
}
pre=node; //TODO: pre 指向 node
if(head==null){
head=node;
}
inOrder(node.right);
}//思路：
//设 pHead1 的长度为 a + c，pHead2 的长度为 b + c，其中 c 为尾部公共部分长度，
//可知 (a + c) + b = (b + c) + a。
//当访问 pHead1 链表的指针访问到链表尾部时，令它从链表 pHead2 的头部开始访问链表 pHead2；
//同样地，当访问 pHead2 链表的指针访问到链表尾部时，令它从链表 pHead1 的头部开始访问链表 pHead1。
//这样就能控制访问 pHead1 和 pHead2 两个链表的指针能同时访问到交点。
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1==null || pHead2==null){
return null;
}
ListNode cur1 = pHead1;
ListNode cur2 = pHead2;
while (cur1!=cur2){
if(cur1==null){
cur1 = pHead2;
}else{
cur1 = cur1.next;
}
if(cur2==null){
cur2 = pHead1;
}else{
cur2 = cur2.next;
}
}
return cur1;
}
//思路：第一步，在每个节点的后面插入复制的节点。
第二步，对复制节点的 random 链接进行赋值。
第三步，拆分。
public RandomListNode Clone(RandomListNode pHead) {
if(pHead==null){
return null;
}
//第一步，在每个节点的后面插入复制的节点
RandomListNode cur=pHead;
while (cur!=null){
RandomListNode newNode = new RandomListNode(cur.label);
newNode.next = cur.next;
cur.next = newNode;
cur=newNode.next;
}
//对复制节点的 random 链接进行赋值。
cur=pHead;
while(cur!=null){
// cur 是当前的节点
// cur.next 是复制的节点
RandomListNode clone = cur.next;
if(cur.random!=null){
clone.random = cur.random.next; //
//cur.random 是 cur 的random 指向的节点
//cur.random.next 就是 cur.random.next 的复制节点
}
cur=clone.next;
}
//拆分
cur=pHead;
RandomListNode pCloneHead = pHead.next;
while(cur.next!=null){ //拆分出 pHead 原来的链表，剩下的就是 pCloneHead 链表
RandomListNode next = cur.next;
cur.next = next.next;
cur=next;
}
return pCloneHead;
}//思路：
//1、如果该节点不是尾节点，那么可以直接将下一个节点的值赋给该节点，
//然后令该节点指向下下个节点，再删除下一个节点，时间复杂度为 O(1)。
//2、如果该节点是尾节点，就需要先遍历链表，找到节点的前一个节点，然后让前一个节点指向 null，
//时间复杂度为 O(N)。
//分析：
// 如果进行 N 次操作，那么大约需要操作节点的次数为 N-1+N=2N-1，
// 其中 N-1 表示 N-1 个不是尾节点的每个节点以 O(1) 的时间复杂度操作节点的总次数，
// N 表示 1 个尾节点以 O(N) 的时间复杂度操作节点的总次数。
// (2N-1)/N 约等于 2，因此该算法的平均时间复杂度为 O(1)。
public ListNode deleteNode(ListNode head, ListNode tobeDelete) {
if(head==null || tobeDelete==null){
return null;
}
if(tobeDelete.next!=null){ //待删除的节点不是尾节点
// 令该节点指向下下个节点，再删除下一个节点，时间复杂度为 O(1)。
ListNode next = tobeDelete.next;
tobeDelete.val = next.val;
tobeDelete.next = next.next;
}else{ //待删除的节点是尾节点
ListNode cur=head;
while (cur.next!=tobeDelete){
cur=cur.next;
}
// cur.next 此时指向 tobeDelete
cur.next=null;
}
return head;
}