算法一 链表（Java实现）
1、LeetCode206反转链表
思路：依次遍历链表节点，每遍历一个节点即逆置一个节点
/** * 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 reverseList(ListNode head) { ListNode pre = null;//指向新链表头节点的指针 ListNode cur = head; while (cur != null) { ListNode nextTemp = cur.next;//备份cur.next cur.next = pre;//更新cur.next pre = cur;//移动pre cur = nextTemp;//遍历链表 } return pre;//返回新链表头节点 } } 复制代码2、LeetCode92反转链表 II
/** * 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 reverseBetween(ListNode head, int left, int right) { int len = right-left+1;//计算需要逆置的节点个数 ListNode pre_head = null;//初始化开始逆置的节点的前驱 ListNode result = head;//最终转换后的链表头节点，非特殊情况即为head while(head!=null && --left!=0){//将head向前移动left-1个位置 pre_head = head;//记录head的前驱 head = head.next; } ListNode modify_list_tail = head;//将modify_list_tail指向当前的head，即逆置后的链表尾 ListNode new_head = null; while(head!=null && len!=0){//逆置len个节点 ListNode nextTemp = head.next; head.next = new_head; new_head = head; head = nextTemp; len--; } modify_list_tail.next = head;//连接逆置后的链表尾与逆置段的后一个节点 if(pre_head!=null){//不是从第一个节点开始逆置 pre_head.next = new_head;//将逆置链表开始的节点前驱与逆置后的头节点连接 } else{ result = new_head;//从第一个节点开始逆置，结果即为逆置后的头节点 } return result; } } 复制代码3、LeetCode160相交链表
思路：1.计算headA、headB链表长度，较长的链表多出的长度
2.将较长链表的指针移动到和较短链表指针对齐的位置
3.headA和headB同时移动，当两指针指向同一个节点时，即找到
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { int get_list_length(ListNode head){//遍历链表，计算链表长度 int len = 0; while(head != null){ len++; head = head.next; } return len; } ListNode forward_long_list(int long_len,int short_len,ListNode head){ int delta = long_len-short_len; while(head != null && delta != 0){ head = head.next;//将指针向前移动至多出节点个数后面的位置 delta--; } return head; } public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int list_A_len = get_list_length(headA); int list_B_len = get_list_length(headB);//求两个链表长度 if(list_A_len > list_B_len){ headA = forward_long_list(list_A_len,list_B_len,headA);//如果链表A长，移动headA到对应位置 }else{ headB = forward_long_list(list_B_len,list_A_len,headB);//如果链表B长，移动headB到对应位置 } while(headA != null&&headB != null){ if(headA == headB){//当两指针指向同一个节点时，说明找到 return headA; } headA = headA.next; headB = headB.next; } return null; } } 复制代码LeetCode题解
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { /** 定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差) 两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度 **/ if(headA == null || headB == null) return null; ListNode pA = headA, pB = headB; // 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头, 而第二轮体现在如果pA或pB相交就返回交点, 不相交最后就是null==null while(pA != pB) { pA = pA == null ? headB : pA.next; pB = pB == null ? headA : pB.next; } return pA; } } 复制代码4、LeetCode142环形链表 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 slow = head, fast = head; ListNode meet = null;//相遇的节点 while(fast != null){ slow = slow.next; fast = fast.next;//slow和fast各先走一步 if (fast == null) { return null;//如果fast遇到链表尾，则返回null } fast = fast.next;//fast再走一步 if (fast == slow){ meet = fast;//fast与slow相遇，记录相遇位置 break; } } if (meet == null) { return null;//如果没有相遇，则证明无环 } while (fast != null && meet != null) { if(head == meet){//当他们相遇，说明遇到环的起始位置 return head; } head = head.next;//head与meet每次走一步 meet = meet.next; } return null; } } 复制代码5、LeetCode86分隔链表
思路：巧用临时头节点
/** * 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 partition(ListNode head, int x) { ListNode less_head = new ListNode(0); ListNode more_head = new ListNode(0);//设置两个临时的头节点 ListNode less_ptr = less_head,more_ptr = more_head;//对应指针指向这两个头节点 while(head != null){ if(head.val < x){//如果节点值小于x，则将该节点插入less_ptr后 less_ptr.next = head; less_ptr = head;//链接完成后，less_ptr向后移动，指向head }else{//否则将该节点插入more_ptr后 more_ptr.next = head; more_ptr = head; } head = head.next;//遍历链表 } less_ptr.next = more_head.next;//将less链表尾，与more链表头相连 more_ptr.next = null;//将more_ptr即链表尾节点next置空 return less_head.next;//less_head的next节点即为新链表头节点，返回 } } 复制代码6、LeetCode138复制带随机指针的链表
深度拷贝：构造生成一个完全新的链表，即使将原链表毁坏，新链表可独立使用
c++：向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。
/* // Definition for a Node. class Node { int val; Node next; Node random;//带有随机指针的链表节点 public Node(int val) { this.val = val; this.next = null; this.random = null; } } */ class Solution { public Node copyRandomList(Node head) { HashMap<Node,Integer> node_map = new HashMap<>();//地址到节点位置的map List<Node> node_vec = new ArrayList<>();//使用vector根据存储节点位置访问地址 Node ptr = head; int i = 0; if(head==null) return null; while(ptr != null){//将新链表节点push入node_vec，生成了新链表节点位置到地址的map node_vec.add(new Node(ptr.val)); node_map.put(ptr,i);//记录原始链表地址至节点位置的node_map ptr = ptr.next;//遍历原始链表 i++;//i记录节点位置 } node_vec.get(0); ptr = head; i = 0; while(ptr != null){//再次遍历原始链表，连接新链表的next指针、random指针 if(i+1>=node_vec.size()){ node_vec.get(i).next = null; }else{ node_vec.get(i).next = node_vec.get(i+1);//连接新链表next指针 } if(ptr.random != null){ int id = node_map.get(ptr.random);//根据node_map确认 node_vec.get(i).random = node_vec.get(id);//原链表random指针指向的位置即id } ptr = ptr.next;//连接新链表random指针 i++; } return node_vec.get(0); } } 复制代码7、LeetCode21合并两个有序链表
思路：比较l1和l2指向的节点，将较小的节点插入到pre指针后，并向前移动较小节点对应的指针。
/** * 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 mergeTwoLists(ListNode l1, ListNode l2) { ListNode temp_head = new ListNode(0);//设置临时头节点temp_head ListNode pre = temp_head;//使用pre指针指向temp_head while(l1 != null&&l2 != null){ if(l1.val < l2.val){ pre.next = l1; l1 = l1.next; }else{ pre.next = l2; l2 = l2.next; } pre = pre.next;//pre指向新连接的节点 } if(l1 != null){ pre.next = l1; } if(l2 != null){ pre.next = l2; } return temp_head.next; } } 复制代码8、LeetCode23合并K个升序链表
思路：对k个链表进行分治，两两进行合并
/** * 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 mergeKLists(ListNode[] lists) { if(lists.length == 0) return null; if(lists.length == 1) return lists[0]; if(lists.length == 2){ return mergeTwoLists(lists[0],lists[1]); } int mid = lists.length/2; ListNode[] sub1_lists = new ListNode[mid]; ListNode[] sub2_lists = new ListNode[lists.length-mid];//拆分lists为两个子lists for(int i = 0; i < mid; i++){ sub1_lists[i] = lists[i]; } for(int i = mid,j = 0; i < lists.length; i++,j++){ sub2_lists[j] = lists[i]; } return mergeTwoLists(mergeKLists(sub1_lists),mergeKLists(sub2_lists));//分治处理 } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; ListNode head = null; if (l1.val <= l2.val){ head = l1; head.next = mergeTwoLists(l1.next, l2); } else { head = l2; head.next = mergeTwoLists(l1, l2.next); } return head; } }
作者：zust_Isabella
链接：https://juejin.cn/post/6987751828691615752