链表的特性：
如下代码：
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode result = new ListNode (3),pre = result;
pre.next = l1;
return result;
}
}
剑指offer 06 从尾到头打印链表
时间复杂度O(n)
空间复杂度O(n)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] reversePrint(ListNode head) {
// 检查链表长度
//注意：node -> 2 -> 3
// node.next = 2 node.next.next = 3 所以不能直接用head.next进while循环
ListNode curNode = head;
int len = 0;
while (curNode != null){
len++;
curNode = curNode.next;
}
//建立一个相同长度的List
int[] l1 = new int[len];
//将链表倒序装入List中
curNode = head;
while(len>0){
l1[len-1] = curNode.val;
curNode = curNode.next;
len--;
}
return l1;
}
}
剑指offer 22 链表中倒数第k个节点
快慢指针，先让快指针走k步，然后两个指针同步走，当快指针走到头时，慢指针就是链表倒数第k个节点。
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode curNode = head;
while(curNode != null){
curNode = curNode.next;
if (k == 0){
head = head.next;
}
else{
k--;
}
}
return head;
}
}
剑指offer 24 反转链表
1 -> 2 -> 3 -> null => 3->2->1->null
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = head;
ListNode cur = null;
while(pre != null){
head = head.next; //将head移至下一位
pre.next = cur; // 修改 next 引用指向
cur = pre; // cur 暂存 pre
pre = head;
}
return cur;
}
}
注解：为何while循环不可以写成：
pre.next = cur; // 修改 next 引用指向
cur = pre; // cur 暂存 pre
head = head.next; //将head移至下一位
pre = head;
因为之前pre和head同时指向了
1 -> 2 -> 3 -> null => 3->2->1->null
而pre.next = cur;已经改变了链表结构，所以后面head = head.next已经不是原本指向的head
剑指offer 25 合并两个排序的链表
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode result = new ListNode(0); //建造一个伪头节点
ListNode temp = result; //temp用来增加节点，result和temp同时指向同一个链表
while(l1 != null && l2 != null){
if(l1.val >= l2.val){
temp.next = l2;
temp = temp.next;
l2 = l2.next;
}
else{
temp.next = l1;
temp = temp.next;
l1 = l1.next;
}
}
if(l1 == null){
temp.next = l2;
}
else if(l2 == null){
temp.next = l1;
}
//抛去伪头节点
return result.next;
}
}
剑指offer 35 复杂链表的复制
HashMap:
class Solution {
public Node copyRandomList(Node head) {
Map<Node,Node> map = new HashMap<>();
Node cur = head;
while(cur != null){
// cur是原来的，在这里充当key; 后者是新建的，充当value
//map{7(old):7(new constructed),13:13,... }
map.put(cur,new Node(cur.val));
cur = cur.next;
}
cur = head;
while(cur != null){
//map.get(cur)是new Node 构造出来的，体现出deep copy
// .next 是做指向。map.get(cur.next)也是新Node
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
//取出,因为cur已经移位到最后了，故用head亦可
return map.get(head);
}
}
合并拆分：
class Solution {
public Node copyRandomList(Node head) {
if(head == null){return null;} //先考虑head =null 情况
Node cur = head;
while(cur != null){
// temp = 7
Node temp = new Node(cur.val);
//temp= 7->13->11->...
temp.next = cur.next;
// cur= 7->7->13->11->...
cur.next = temp;
//cur= 13->11->...
cur = temp.next;
}
//调整cur至最前node
cur = head;
//匹配random
while(cur != null){
//不能同时处理random和next原因是：当设定 7->7->3->3->...新7next为新3时，链表断裂无法进行
// cur.next.next = cur.next.next.next;
if(cur.random != null){
cur.next.random = cur.random.next;
}
cur = cur.next.next;
}
// 拆分两链表
cur = head.next;
Node pre = head, res = head.next;
while(cur.next != null) {
pre.next = pre.next.next;
cur.next = cur.next.next;
pre = pre.next;
cur = cur.next;
}
pre.next = null; // 必须要把head也还原好，不要忘了单独处理原链表尾节点
return res; // 返回新链表头节点
}
}
剑指offer 52 两个链表的第一个公共节点
双指针解法：双方在最后加上对方不同的部分，最终会相遇
时间:O(M+N) 两个链表长度 空间: O(1)
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode hA = headA;
ListNode hB = headB;
//双指针： uncommonA+common+B = uncommonB+common+A
while(hA != hB){
if(hA == null){hA = headB;}
else hA = hA.next;
if(hB == null){hB = headA;}
else hB = hB.next;
}
return hA;
}
}
剑指offer 18 删除链表的节点*
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
class Solution {
public ListNode deleteNode(ListNode head, int val) {
// 引入伪头节点
ListNode dummyhead = new ListNode(0);
dummyhead.next = head;
// 指针cur开始进行判定
ListNode cur = dummyhead;
while(cur.next != null){
if(cur.next.val != val){
cur = cur.next;
}
else {
cur.next = cur.next.next;
}
}
// 返回
return dummyhead.next;
}
}
