鏈表的特性：
如下代碼：
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode result = new ListNode (3),pre = result;
pre.next = l1;
return result;
}
}
劍指offer 06 從尾到頭打印鏈表
時(shí)間復(fù)雜度O(n)
空間復(fù)雜度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) {
// 檢查鏈表長(zhǎng)度
//注意：node -> 2 -> 3
// node.next = 2 node.next.next = 3 所以不能直接用head.next進(jìn)while循環(huán)
ListNode curNode = head;
int len = 0;
while (curNode != null){
len++;
curNode = curNode.next;
}
//建立一個(gè)相同長(zhǎng)度的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 鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)
快慢指針亩码，先讓快指針走k步瓮孙，然后兩個(gè)指針同步走鲁僚，當(dāng)快指針走到頭時(shí)祈搜，慢指針就是鏈表倒數(shù)第k個(gè)節(jié)點(diǎn)比搭。
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 反轉(zhuǎn)鏈表
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循環(huán)不可以寫成：
pre.next = cur; // 修改 next 引用指向
cur = pre; // cur 暫存 pre
head = head.next; //將head移至下一位
pre = head;
因?yàn)橹?code>pre和head同時(shí)指向了
1 -> 2 -> 3 -> null => 3->2->1->null
而pre.next = cur;已經(jīng)改變了鏈表結(jié)構(gòu)擦囊，所以后面head = head.next已經(jīng)不是原本指向的head
劍指offer 25 合并兩個(gè)排序的鏈表
輸入：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); //建造一個(gè)偽頭節(jié)點(diǎn)
ListNode temp = result; //temp用來增加節(jié)點(diǎn)蝗羊，result和temp同時(shí)指向同一個(gè)鏈表
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;
}
//拋去偽頭節(jié)點(diǎn)
return result.next;
}
}
劍指offer 35 復(fù)雜鏈表的復(fù)制
HashMap:
class Solution {
public Node copyRandomList(Node head) {
Map<Node,Node> map = new HashMap<>();
Node cur = head;
while(cur != null){
// cur是原來的，在這里充當(dāng)key; 后者是新建的，充當(dāng)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 構(gòu)造出來的，體現(xiàn)出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;
}
//取出,因?yàn)閏ur已經(jīng)移位到最后了骤菠，故用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;
}
//調(diào)整cur至最前node
cur = head;
//匹配random
while(cur != null){
//不能同時(shí)處理random和next原因是：當(dāng)設(shè)定 7->7->3->3->...新7next為新3時(shí)，鏈表斷裂無法進(jìn)行
// 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也還原好疤孕，不要忘了單獨(dú)處理原鏈表尾節(jié)點(diǎn)
return res; // 返回新鏈表頭節(jié)點(diǎn)
}
}
劍指offer 52 兩個(gè)鏈表的第一個(gè)公共節(jié)點(diǎn)
雙指針解法：雙方在最后加上對(duì)方不同的部分商乎，最終會(huì)相遇
時(shí)間:O(M+N) 兩個(gè)鏈表長(zhǎng)度 ? 空間: 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 刪除鏈表的節(jié)點(diǎn)*
輸入: head = [4,5,1,9], val = 5
輸出: [4,1,9]
class Solution {
public ListNode deleteNode(ListNode head, int val) {
// 引入偽頭節(jié)點(diǎn)
ListNode dummyhead = new ListNode(0);
dummyhead.next = head;
// 指針cur開始進(jìn)行判定
ListNode cur = dummyhead;
while(cur.next != null){
if(cur.next.val != val){
cur = cur.next;
}
else {
cur.next = cur.next.next;
}
}
// 返回
return dummyhead.next;
}
}
