0. Abstract

class ListNode(object,val):
	def __init__(self，val):
		self.val=val
		self.next=None 

struct ListNode {
  int val;
  ListNode* next;
  ListNode(): val(0), next(nullptr) {}
  ListNode(int x): val(x), next(nullptr) {}
  ListNode(int x, ListNode* next): val(x), next(next) {}
};

基础类-翻转链表
// 206.翻转链表 --cur_node->next先存后覆盖，cur_node用完后变成前任，继续去找下一任。
ListNode* reverseList(ListNode* head);

基础类-节点删除
// 203.移除链表元素 --给定要删val(多个)，发生删除不动pre_node, 仅更新cur_node。
ListNode* removeElements(ListNode* head, int val);
// 237.删除链表中的节点 --给定要删Node，用next_node覆盖cur_node, cur_node就没了(拿不到pre_node)。一个循环都不用 [a] node不是最后一个节点
void deleteNode(ListNode* node);                        
// 19.删除链表的倒数第N个结点 --先做定位倒数第k 再删除。
// 没有假定. 可能是最后一个节点, 所以不能直接用deleNode里的直接覆盖(有pre)
ListNode* removeNthFromEnd(ListNode* head, int n);

基础类-节点定位
// 面试题02.02.返回倒数第k个节点 -- left_p与right_p相差k-step, 就是k个节点。[a] k有效
int kthToLast(ListNode* head, int k);
// 876.链表的中间结点 --循环结束时：奇数个节点，fast_p指向最后一个节点；偶数个节点，fast_p指向nullptr  
ListNode* middleNode(ListNode* head);


提升-双指针
// 21.合并两个有序链表- 从头开始覆盖类-dummy_head + dummy_node
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)；
// 160.相交链表 --一个while(a_p != b_P)
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)；
// 141.环形链表 --一个while(fast_p非空 && fast_p->next非空)
bool hasCycle(ListNode *head);
// 142.环形链表2 --相遇后再让fast从头一步一步跑
ListNode *detectCycle(ListNode *head);
// 83.删除排序链表中的重复元素 --双指针 + 节点删除 right_p != nullptr
ListNode* deleteDuplicates(ListNode* head)；

Tips：

1. 使用节点前确定其非空，例如： fast_p = fast_p.next.next 需要检查 fast_p 和 fast_p.next 不为空。

2. 链表调试不易，多测试几个用例总是很有用的，可输出node.val来debug。

3. 常用变量名组：(pre_node, cur_node, next_node)、 (right_p, left_p)、(fast_p, slow_p)，traversal链表时这三类常组团配套出现。

4. 可能会删除head的操作 常使用dummy节点来保证head被删除后还能正常链接到链表的其他部分。

1. Introduction

链表 是一种线性结构，每个元素都是一个单独对象；所有元素通过 对象引用字段 链接在一起，

一个元素通常称为一个节点，大多数情况下，我们使用头结点(head)来表示整个链表。

类型：单链表(single-linked-list)、双链表(doubly-linked-list)

class SinglyListNode(object,val):
	def __init__(self，val):
		self.val = val        # 节点值
		self.next = None      # 链接下一个节点的引用字段

class DoublyListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

1. 给定head, 访问链表任意节点的时间复杂度为O(n)；每次访问都需要从head开始往后逐节点traversal， 无法在常量时间内完成的。【数组 访问任意元素的时间复杂度是O(1)，使用index实现】
2. 给定cur_node, 删除cur_node 和 将new_node插入cur_node.next 的时间均复杂度为O(1)。【数组 给定插入位置后，其后所有的元素都要移动位置】
3. 给定cur_node, 双链表删除pre_node时间复杂度为O(1), 单链表删除pre_node时间复杂度为O(n)。【单链表无法由给定节点获取前一个节点，因此在删除给定节点之前必须花费o(n)的时间来找出前一个节点】

主要优势：插入、删除节点十分方便

// 插入节点
cur_node = xxxx  								// 找到插入位置 cur_node 
new_node = ListNode(new_val, cur_node.next);    // new_node.next 装载 cur_node.next
cur_node.next = new_node;                       // cur_node.next 覆盖为 new_node

// 删除节点 way1 - 前一个节点 链接 下一个节点; 需要找到 pre_node cur_node next_node
// cur_node将会悬空，无法通过head找到它，虽然它的cur_node.next 指向 next_node, 但是没什么用
pre_node.next = next_node 

// 删除节点 way2 - 当前节点 覆盖为 下一个节点;
// cur_node 取代了next_node的功能，next_node悬空，没人指向它。
cur_node.val = next_node.val;
cur_node.next = next_node.next

2. 自定义链表类

2.1 自定义链表类1-使用单链表

单链表节点有两个属性：val、next。val是当前节点的值，next是指向下一个结点的指针/引用。在自定义链表类中实现：（链表实现index操作）

# 1. get(index): 获取链表第index个节点，如果索引无效，则返回-1（index 从0开始）
# 2. addAtHead(val): 在链表的第一个结点前添加一个值为val的结点。插入后，新节点将成为链表的第一个结点
# 3. addAtTail(val): 将值为val的节点追加为链表的最后一个元素
# 4. addAtIndex(index,val)：在链表的第index个节点前添加值为val的结点。如果index为链表的长度，则将该结点按附加到链表的末尾。如果index大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
# 5. deleteAtIndex(index)：如果索引有效则删除链表的第index个结点。

class ListNode:
    def __init__(self,x):
        self.val = x
        self.next = None
        
class MyLinkedList(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.size = 0
        self.head = ListNode(0)
        
    def get(self, index):
        """
        Get the value of the index-th node in the linked list. If the index is invalid, return -1.
        """
        if index < 0 or index >= self.size:
            return -1
        node = self.head
        for _ in range (index+1):  # index 从0开始 
            node = node.next
        return node.val
        
    def addAtHead(self, val):
        """
        Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
        """
        self.addAtIndex(0,val)
        
    def addAtTail(self, val):
        """
        Append a node of value val to the last element of the linked list.
        """
        self.addAtIndex(self.size,val)

    def addAtIndex(self, index, val):
        """
        Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
        """
        if index > self.size:
            return
        if index < 0:
            index = 0
        self.size += 1
        pred = self.head
        for _ in range(index): #[0,index-1]
            pred = pred.next
        node = ListNode(val)
        node.next = pred.next
        pred.next = node

    def deleteAtIndex(self, index):
        """
        Delete the index-th node in the linked list, if the index is valid.
        """
        if index < 0 or index >= self.size:
            return
        self.size -= 1
        pred = self.head
        for _ in range(index): # [0,index-1]
            pred = pred.next
        pred.next = pred.next.next

2.2 自定义链表类2-使用双链表

在自定义链表类中实现：

# 1. get(index): 获取第index个节点的值，如果索引无效则返回-1
# --index从0开始，因此初始化curr=self.head之后，需要往后在操作index+1次即[0,index]

# 2. addAtHead(val): 在链表的第一个元素之前家一个值为val的节点，插入后，新节点将成为链表的第一个节点。
# --pred=self.head(伪头节点)，succ=self.head.next

# 3. addAtTail(val): 将值为val的节点追加到链表的最后一个元素
# --succ=self.tial(伪尾节点)，pred=self.tail.prev

# 4. addAtIndex(index,val): 在链表中的第index个节点之前加入值为val的节点，如果index等于链表长度，则该节点将附加于链表的末尾。如果index大于链表的长度则不会加入节点。如果index小于0，则在头部添加节点。
# --第index个节点为succ节点，index-1个节点为pred节点。
# --从前往后：pred=self.head(初始化)再操作[0,index-1]次；
# --由后往前：succ=self.tail(初始化)再操作[index,size-1]次（size-index次）

# 5. deleteAtIndex(index): 如果索引index有效，则删除链表中的第index个节点。
# --由前往后：找到第index-1个节点为pred [0,inde1],succ=pred.next.next；
# --由后往前：找到index+1个节点为succ.

class ListNode:
    def __init__(self,x):
        self.val=x
        self.next=None
        self.prev=None
        
class MyLinkedList(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.size=0
        self.head,self.tail=ListNode(0),ListNode(0)
        self.head.next=self.tail     # 这两句的作用是什么，变成一个环？
        self.tail.prev=self.head
        
    def get(self, index):
        """
        Get the value of the index-th node in the linked list. If the index is invalid, return -1.
        :type index: int
        :rtype: int
        """
        if index<0 or index>=self.size:
            return -1
        if index+1<self.size-index:
            curr=self.head
            for _ in range(index+1): # [0,index]
                curr=curr.next
        else:
            curr=self.tail
            for _ in range(self.size-index):
                curr=curr.prev
        return curr.val

    def addAtHead(self, val):
        """
        Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
        :type val: int
        :rtype: None
        """
        pred,succ=self.head,self.head.next
        self.size+=1
        to_add=ListNode(val)
        to_add.prev=pred
        to_add.next=succ
        pred.next=to_add
        succ.prev=to_add

    def addAtTail(self, val):
        """
        Append a node of value val to the last element of the linked list.
        :type val: int
        :rtype: None
        """
        succ,pred=self.tail,self.tail.prev
        self.size+=1
        to_add=ListNode(val)
        to_add.prev=pred
        to_add.next=succ
        pred.next=to_add
        succ.prev=to_add
        

    def addAtIndex(self, index, val):
        """
        Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
        :type index: int
        :type val: int
        :rtype: None
        """
        if index>self.size:
            return
        if index<0:
            index=0
        if index<self.size-index:
            pred=self.head
            for _ in range(index):
                pred=pred.next
            succ=pred.next
        else:
            succ=self.tail
            for _ in range(self.size-index):
                succ=succ.prev
            #print(succ.val)
            pred=succ.prev
        
        self.size+=1
        to_add=ListNode(val)
        #print(pred.val,succ.val,to_add.val)
        to_add.prev=pred
        to_add.next=succ
        pred.next=to_add
        succ.prev=to_add
        
    def deleteAtIndex(self, index):
        """
        Delete the index-th node in the linked list, if the index is valid.
        :type index: int
        :rtype: None
        """
        if index<0 or index>=self.size:
            return
        if index<self.size-index:
            pred=self.head
            for _ in range(index):
                pred=pred.next
            succ=pred.next.next
        else:
            succ=self.tail
            for _ in range(self.size-index-1):
                succ=succ.prev
            pred=succ.prev.prev
        self.size-=1
        pred.next=succ
        succ.prev=pred

注意点：删除插入，最重要的是找到前驱和后继节点，可以双向操作之后需要判断由前往后，还有由后往前。

3. 基础+双指针技巧

两类双针：

1. 两个指针从不同的位置出发(速度相同)：两端向中间、起点不同方向相同 【left_p, right_p】
2. 两个指针以不同的速度移动：一个指针快一些，另一个指针慢一些 【slow_p, fast_p】

相关题型：

1. 求节点位置类：设置好快慢指针的间距 【倒数第n个节点，中间节点】
2. 求交点类： 想方法 让两个指针走过相同的路径 【入环点，相交点】

3.1 反转链表

206.反转链表 – 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
迭代求解 – 常用解

    def reverseList(self, head: ListNode) -> ListNode:
        """
        @note 遍历每个节点，记录next的内容(下一个节点)，并且更新next内容为上一个节点
        """
        previous_node = None
        current_node = head
        while(current_node):                # 循环退出条件，当前的节点为空
            next_node = current_node.next   # 信息更新流，被覆盖的东西要先保留下来
            current_node.next = previous_node
            previous_node = current_node
            current_node = next_node
        return previous_node                # 退出循环时current_node 为空，pre_node是有效的

递归求解 – 少用：假设链表的其余部分都已经被翻转，现在该如何翻转它前面的部分。由最后一个开始往前不断翻转

class Solution(object):
    def reverseList(self, head):
        if head==None or head.next==None:
            return head
        p=self.reverseList(head.next)   # 记录最后一个结点作为头指针用的。
        head.next.next=head             # head 有些歧义，最好是改成node
        head.next=None
        return p

3.2 节点删除(定值、定节点)

203.移除链表元素 – 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* pre_node = dummy;
        ListNode* cur_node = head;
        while(cur_node != nullptr) {
            if (cur_node->val == val) {    // 链表中存在多个val
                pre_node->next = cur_node->next;
                cur_node = cur_node->next;
            } else {
                pre_node = cur_node;
                cur_node = cur_node->next;
            }
        }
        return dummy->next;
    }
};

237.删除链表中的节点 – 给定要删Node， 用next_node覆盖cur_node, cur_node就没了(拿不到pre_node)。 [a] node不是最后一个节点

class Solution {
public:
    void deleteNode(ListNode* node) {
        if (node != nullptr && node->next != nullptr) {
            node->val = node->next->val;
            node->next = node->next->next;
        }
    }
};

3.3 节点定位(中间节点、倒数第k个节点)

面试题 02.02. 返回倒数第 k 个节点

class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        ListNode* right_p = head;
        ListNode* left_p = head;
        for (int i = 0; i < k; i++) {
            right_p = right_p->next;
        }
        while(right_p != nullptr) {
            right_p = right_p->next;
            left_p = left_p->next;
        }
        return left_p->val;
    }
};

876.链表的中间结点 – 给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* fast_p = head;
        ListNode* slow_p = head;
         // 循环结束时， 奇数个节点，fast_p位于最后一个节点, 从head开始，能走的节点数(n-1)为偶数，正好fast_p走到最后一个节点
         //            偶数个节点，fast_p位于nullptr的位置上，从head开始，能走的节点数(n-1)为偶数，正好fast_p走出了最后一个节点
        while(fast_p != nullptr and fast_p->next != nullptr) {
            fast_p = fast_p->next->next;
            slow_p = slow_p->next;
        }
        return slow_p;
    }
};

3.4 删除链表倒数第N个节点

19.删除链表的倒数第N个结点 – 第K个节点 + 删除节点 两题合并

class Solution(object):
    def removeNthFromEnd(self, head, n):
        dummy=ListNode(0)
        dummy.next=head
        first,second=dummy,dummy
        #irst.next,second.next=head,head
        for i in range(n):
            first=first.next
        while(first.next!=None):
            second=second.next
            first=first.next
        second.next=second.next.next
        return dummy.next

3.5 合并两个有序链表

21.合并两个有序链表 – 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy = new ListNode(0, nullptr);
        ListNode* cur_node = dummy;
        while(list1 || list2) {
            if (list2 == nullptr || (list1 != nullptr && list1->val < list2->val)) {
                cur_node->next = new ListNode(list1->val, nullptr);
                cur_node = cur_node->next;
                list1 = list1->next;
            } else {
                cur_node->next = new ListNode(list2->val, nullptr);
                cur_node = cur_node->next;
                list2 = list2->next;
            }
        }
        return dummy->next;
    }
};

python 迭代+递归

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy_head = ListNode(0)
        node_p = dummy_head
        while(list1 or list2):
            if (list2 is None or (list1 is not None and list1.val < list2.val)):
                node_val = list1.val
                list1 = list1.next
            else:
                node_val = list2.val
                list2 = list2.next
            node_p.next = ListNode(node_val)
            node_p = node_p.next
        return dummy_head.next

# 递归最重要的是递归出口
# 由顶向下时，已经决定了第一个节点是谁，递归得到最底端时，直接将长链表的剩余部分链接回已经排序好的链表中。
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        if l1==None:
            return l2
        elif l2==None:
            return l1
        elif l1.val<=l2.val:
            l1.next=self.mergeTwoLists(l1.next,l2)
            return l1      
        else:
            l2.next=self.mergeTwoLists(l1,l2.next)
            return l2

3.6 相交链表

160. 相交链表 – 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

解：速度一样，走过相同的路径，如果有交点，必定会在交点处相遇
创建两个指针 pa和 pb，分别初始化为链表 A 和 B 的头结点。然后让它们向后逐结点遍历。当 pa 到达链表的尾部时，将它重定位到链表 B 的头结点 ; 类似的，当 pb 到达链表的尾部时，将它重定位到链表 A 的头结点。若在某一时刻 pa 和 pb 相遇，则 pa/pb 为相交结点。

// 如果不相交，a_p, b_p 遍历完两个链表，同时到达对方链表结尾null (如果A和B同样长，a_p和b_p遍历完自己就能得出答案。
// 如果相交， a_p, b_p 走过相同数量的节点后，相遇在链表交点
// 每个指针 最多走过的节点数 len(A) + len(B)
class Solution {
public:
    ListNode *getIntersectionNode(ListNode* headA, ListNode* headB) {
        ListNode* a_p = headA;
        ListNode* b_p = headB;
        while(a_p != b_p) {
            if (a_p == NULL) {
                a_p = headB;
            } else {
                a_p = a_p->next;
            }

            if (b_p == NULL) {
                b_p = headA;
            } else {
                b_p = b_p->next;
            }
        }
        return a_p;
    }

3.7 环形链表(有无、入环节点)

141.环形链表 – 给你一个链表的头节点 head ，判断链表中是否有环。
解法1-快慢指针 – 常用解：快指针一次跑两步，慢指针一次跑一步。如果无环，则快指针将先到达尾部；如果有环，快慢指针终将相遇。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fast_p = head;
        ListNode* slow_p = head;
        while(fast_p != NULL and fast_p->next != NULL) {
            fast_p = fast_p->next->next;
            slow_p = slow_p->next;
            if (slow_p == fast_p) {
                return true;
            }
        }
        return false;
        
    }
};

解烦2-hash表解：

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head==None or head.next==None:
            return False
        has=[]
        r1=head
        while(r1):
            if r1 in has:
                return True
            has.append(r1)
            r1=r1.next
        return False

142.环形链表 II – 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 (返回节点)
解法1-快慢指针,弗洛伊德算法： 快慢指针会相遇，但不是在环的起点处，需要再遍历一次才能找到环的起点。假设：

1. 第一次相遇时slow_p走过k 步（那fast_p就走过了2k步）
2. 相遇点距离环起点m步
3. 环的周长为c

则有：

1. fast_p第一次经过相遇点(距离起始点也是走过了k个节点)，两者相遇在相遇点时，fast_p比slow_p多走了k步， 这k步都消耗在转圈圈上了， 所以有k = nc。
2. 相遇后，让slow_p从头开始走， fast_p从相遇点开始走，再次相遇的时候，就是环的起点
   一方面：fast_p从相遇点再走k步，还是会回到相遇点。那么倒退m步，也就是再走k-m步，就会回到环的起点。
   另一方面-从头到环的起点的距离也是k-m.
3. (小推论)第一次相遇时，slow_p 没有在环里绕过圈;
   case1：slow_p刚进环时，两者未相遇，fast_p离环起点a步； 第一次相遇时，slow_p 又走过t步，fast_p则又走了2t步；2t = (c - a + t) [c-a 为两者起点差距, t 为slow_p又走出来的差距] 即 t = c - a. 因为 k > 0, 所以t < c, 成为周长, 则slow_p 没有在环里绕过圈。
   case2: slow_p刚进环时，两者未相遇, slow_p 没有在环里绕过圈。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast_p = head;
        ListNode* slow_p = head;
        while(fast_p != NULL && fast_p->next != NULL) {
            fast_p = fast_p->next->next;
            slow_p = slow_p->next;
            if (fast_p == slow_p) {
                break;
            }
        }
        if (fast_p == NULL || fast_p->next == NULL) {
            return NULL;
        }
        fast_p = head;
        while(fast_p != slow_p) {
            fast_p = fast_p->next;
            slow_p = slow_p->next;
        }
        return fast_p;
    }
};

解法2- hash表： 思路在上题的基础上，如果有环，返回入环节点，而非true即可

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head==None or head.next==None:
            return None
        has=[]
        r1=head
        while(r1):
            if r1 in has:
                return r1
            has.append(r1)
            r1=r1.next
        return None

3.8 删除排序链表中的重复元素

83.删除排序链表中的重复元素 – 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

26.删除有序数组中的重复项 – 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

27.移除元素 – 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

class Solution {
public:
	// 83. 删除排序链表中的重复元素 
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy = new ListNode(-101, head);
        ListNode* right_p = dummy;
        ListNode* left_p = dummy;
        while(right_p != nullptr) {
            if (right_p->val != left_p->val) {
                left_p->next = right_p; // 
                left_p = left_p->next;
            }
            right_p = right_p->next;
        }
        left_p->next = nullptr;  // 截断后续
        return dummy->next;
    }
    
	// 26. 删除有序数组中的重复项
    int removeDuplicates(vector<int>& nums) {
        int right = 0;
        int left = 0;
        int n = nums.size();
        while(right < n) {
            if (nums[right] != nums[left]) {
                left++;                 // nums[left]有效，nums[left+1]待填充
                nums[left] = nums[right];
            } 
            right++;
        }
        return left+1;
    }
    
    // 27.移除元素
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int left = 0;
        int right = 0;
        while(right < n) {
            if (nums[right] != val) {
                nums[left] = nums[right];  // nums[left] 待填充，nums[left-1]有效
                left++;
            } 
            right++;
        }
        return left;
    }
    
};

4. 链表扩展

4.1 奇偶链表

给定一个单链表，把所有奇数节点和偶数节点（节点 编号的奇偶性）分别排在一起。
思路1：原来的链表分成奇偶两个子链表，然后将偶链表链接到奇链表后面。
没有使用额外的空间，直接从原来的链表中截取。

class Solution(object):
    def oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head==None:
            return head
        even_h=ListNode(0)
        even_node=even_h
        cur_node=head
        i=1
        while(cur_node):
            next_node=cur_node.next
            if i %2==0:
                cur_node.next=None   # 将node.next的值给设置为零，能防止成环
                even_node.next=cur_node
                even_node=even_node.next
                pre_node.next=next_node
                
            else:
                pre_node=cur_node
            cur_node=next_node
            i+=1
        cur_node=head.next
        pre_node=head
        while(cur_node):
            print(pre_node.val)
            pre_node=cur_node
            cur_node=cur_node.next
        pre_node.next=even_h.next
        return head        

4.2 回文链表

判断一个链表是否为回文链表。
o(n)时间复杂度，o(1)空间复杂度

思路1：可以先把链表装进数组中，判断数组中元素是否构成回文。数组的前后遍历比单链表方便。时间复杂度o(n)，空间复杂度o(n)

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return True
        lst=[]
        p=head
        while(p):
            lst.append(p.val)
            p=p.next
        return lst==lst[::-1]

思路2：翻转原链表，对照两个链表是否一致，如果回文链表应该是一致的，反之原链表不为回文链表。时间复杂度o(n),空间复杂度o(n)

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """

        if head==None or head.next==None:
            return True
        # 备份原链表
        head_be=ListNode(0)
        node=head
        node_be=head_be    
        while(node):
            node_be.next=ListNode(node.val)
            node_be=node_be.next
            node=node.next
        # 转置原链表
        pre_node=None
        cur_node=head
        while(cur_node):
            next_node=cur_node.next
            cur_node.next=pre_node
            pre_node=cur_node
            cur_node=next_node
        # 比较两个链表
        node_be=head_be.next
        node_af=pre_node
        while(node_be and node_af):
            if node_be.val!=node_af.val:
                return False
            node_be=node_be.next
            node_af=node_af.next
        return True

思路三：避免使用 O(n)O(n) 额外空间的方法就是改变输入。

我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，因为使用该函数的人不希望链表结构被更改。

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next:
            return True
        # 计算链表长度
        p1=head
        n=1
        while(p1.next):
            p1=p1.next
            n+=1
        p1=head
        p2=head
        if n==2:
            if  head.val==head.next.val:
                return True
            else:
                return False
        # 找链表中点
        for i in range(int(round(n/2.0))-1): # 0
            p1=p1.next
        half_end=p1     # 前一半链表的最后一个节点
        # 翻转后一半链表
        p1=p1.next
        pre_node=None
        for i in range(int(n/2.0)): # 0,1
            next_node=p1.next
            p1.next=pre_node
            pre_node=p1
            p1=next_node
        half_end.next=pre_node
        p1=head
        # 比较前一半和翻转后的后一半。
        for i in range(int(round(n/2.0))): # 0,1
            p1=p1.next
        for i in range(int(n/2)):# 0,1
            if p1.val!=p2.val:
                return False
            p1=p1.next
            p2=p2.next
        
        return True

4.3 两数相加

给出两个 非空的链表 来表示两个 非负整数。其中，他们各自的位数是按照 逆序 方式存储的，并且每个节点只能存储一位 数字。

如果，我们将这两个数相加起来，返回一个新的链表表示它们的和

可以假设除了数字0之外，两个数字都不会以0开头

思路：逆序存储简化了问题，直接遍历两个链表的对位元素，相加后维护一个进位标志flag。
冗余

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        flag=0
        res_head=ListNode(0)
        res_cur_node=res_head
        while(l1 and l2):
            sum_num=l1.val+l2.val+flag
            flag=sum_num//10
            res_cur_node.next=ListNode(sum_num%10)
            res_cur_node=res_cur_node.next
            l1=l1.next
            l2=l2.next
        while(l1):
            #print(l1.val)
            sum_num=l1.val+flag
            flag=sum_num//10
            res_cur_node.next=ListNode(sum_num%10)
            res_cur_node=res_cur_node.next
            l1=l1.next
        while(l2):
            #print(l2.val)
            sum_num=l2.val+flag
            flag=sum_num//10
            res_cur_node.next=ListNode(sum_num%10)
            res_cur_node=res_cur_node.next
            l2=l2.next
        if flag:
            res_cur_node.next=ListNode(flag)
        return res_head.next

精简

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        carry=0
        res_head=ListNode(0)
        res_cur_node=res_head
        
        while(l1 or l2 or carry):
            if l1:
                carry+=l1.val
                l1=l1.next
            if l2:
                carry+=l2.val
                l2=l2.next
            carry,val=divmod(carry,10)
            res_cur_node.next=ListNode(val)
            res_cur_node=res_cur_node.next
        return res_head.next

4.4 扁平化多级双向链表

多级双向链表中，除了指向下一个节点和前一个节点的指针外，它还有一个子链表指针，可能指单独的双向链表。这些子链表也可能有一个或多个自己的子项。一次类推，生成多级数据结构 。

给出位于链表第一级的头节点，请扁平化链表，使所有的节点出现子啊单级双链表中。

直觉：采用递归的方式求解，可每个节点该如何处理呢：
新建一个res_head,res_head下一个节点应该为curr_node.child,curr_node.next,

官方思路递归：扁平化处理可以看作对二叉树进行先序遍历，child作为二叉树中的指向座子树的left指针，next可以看作二叉树中的right指针。
难点：深度优先遍历到了末尾该如何让扁平化操作？
flatten_dfs(prev, curr)接收两个指针作为函数参数，并返回扁平化链表中的尾部指针。curr指向需要扁平化的子列表，prev指向curr元素的前一个元素。
在dfs函数中首先要建立prev和curr的双向链接
然后对左子树进行操作dfs(curr,cuur.child)其将返回扁平化子列表的尾部元素，再调用dfs(tail,curr.next)对右子树进行操作。注意点：
1.在进行左子树操作时，需要先保存curr.next的信息
2.在扁平化child指针所指向的列表之后，应该删除child指针

"""
class Solution(object):
    def flatten(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if head==None:
            return head
        dummy_head=Node(None,None,head,None)
        self.flatten_dfs(dummy_head,head)
        dummy_head.next.prev=None
        return dummy_head.next
        
    def flatten_dfs(self,prev,curr):
        if curr==None:
            return prev
        curr.prev=prev
        prev.next=curr
        tempNext=curr.next
        tail=self.flatten_dfs(curr,curr.child)
        curr.child=None
        return self.flatten_dfs(tail,tempNext)

官方思路迭代：

4.5 复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点
编程实现这个链表的深度拷贝

难点：新建节点，很简单，随机节点该如何指向？

先遍历一遍形成一个单链表，再遍历一遍原链表找到带随机指针的节点，在单链表中找到对应的节点，难的是对应节点怎么找，因为，指针存的是地址，在新链表中并不知道该指向哪一个？解决方案 – 维护一张map映射表，每个节点对应的新节点，因此便可以找到对应的节点。

class Solution(object):
    def copyRandomList(self, head):
        if head==None:
            return None
        visitedHash={}
        res_head=Node(0)
        res_cur_node=res_head
        cur_node=head
        while(cur_node):
            node=Node(cur_node.val,None,None)
            res_cur_node.next=node
            visitedHash[cur_node]=node
            res_cur_node=res_cur_node.next
            cur_node=cur_node.next
        cur_node=head
        res_cur_node=res_head.next
        while(cur_node):
            if cur_node.random:
                node=visitedHash[cur_node.random]
                res_cur_node.random=node
            cur_node=cur_node.next
            res_cur_node=res_cur_node.next
        return res_head.next

参考官网给题解：递归
带随机指针的链表可以看作一张图，要做的是遍历整张图，并拷贝它。拷贝的意思是每当遇到一个新的未访问过的节点，需创造新的节点。在回溯的过程中记录访问过的节点，否则因为随机指针存在，会导致死循环。

class Solution(object):
    def __init__(self):
        self.visitedHash={}
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if head==None:
            return None
        if head in self.visitedHash:
            return self.visitedHash[head]
        node=Node(head.val,None,None)
        self.visitedHash[head]=node
        node.next=self.copyRandomList(head.next)
        node.random=self.copyRandomList(head.random)
        return node

4.6 旋转链表

给定一个链表，将链表的每个节点向右移动k个位置，其中k是非负数。
思路1:和旋转数组一样，每次右移一位，移动K次即可

class Solution(object):
    def rotateRight(self, head, k):
        if head==None or head.next==None:
            return head
        l=0
        cur_node=head
        while(cur_node):
            l+=1
            cur_node=cur_node.next
        k=k%l
        def rotate_one_step(head):
            pre_pre_node=None
            pre_node=head
            cur_node=head.next
            while(cur_node):
                pre_pre_node=pre_node
                pre_node=cur_node
                cur_node=cur_node.next
            pre_pre_node.next=None
            pre_node.next=head
            return pre_node
        while(k>0):
            head=rotate_one_step(head)
            k-=1
        return head         

思路2: 移动k次，就是将倒数的k个节点相对顺序不变的移动到链表的头部。所以从链表的head开始，往后找到L-k个节点，将后半部分移动到链表的前半部分。

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if head==None or head.next==None:
            return head
        l=0
        cur_node=head
        while(cur_node):
            l+=1
            cur_node=cur_node.next
        k=k%l
        # 首尾相连
        pre_node=None
        cur_node=head
        while(cur_node):
            pre_node=cur_node
            cur_node=cur_node.next
        pre_node.next=head
        # 寻找切割点
        cur_node=head
        for _ in range(1,l-k): #[0,l-k-1]
            cur_node=cur_node.next
        # 确定的新的头部
        new_head=cur_node.next
        cur_node.next=None
        return new_head