1. 剑指 Offer 18. 删除链表的节点


1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if not head:return head
        if head.val==val:return head.next
        pre,cur = head,head.next
        while(cur):
            if cur.val != val:
               pre,cur = cur,cur.next
            else:
                pre.next = cur.next
                break
        return head

2. 剑指 Offer 22. 链表中倒数第k个节点


1
2
3
4
5
6
7
8
9
10
class Solution:
    def getKthFromlatter(self, head: ListNode, k: int) -> ListNode:
        former,latter = head,head
        while(k):
            latter = latter.next
            k-=1
        while(latter):
            former,latter = former.next,latter.next
        return former

3.剑指 Offer 24. 反转链表


1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = NULL, *pre = head;
        while (pre != NULL) {
            ListNode* t2 = pre->next;
            pre->next = cur;
            cur = pre;
            pre = t;
        }
        return cur;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        cur = None 
        pre = pHead
        while(pre):
            tmp = pre.next
            pre.next = cur
            cur = pre
            pre = tmp
        return cur

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode cur = null;
        ListNode pre = head;
        while(pre != null){
            ListNode tmp = pre.next;
            pre.next = cur;
            cur = pre;
            pre = tmp;
        }
        return cur;
    }
}

4. 剑指 Offer 25. 合并两个排序的链表

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        cur = l3_pre = ListNode(0)
        while(l1 and l2):
            if l1.val<l2.val:
                cur.next,l1 = l1,l1.next
            else:
                cur.next,l2 = l2,l2.next
            cur  = cur.next
        cur.next = l1 if l1 else l2
        return l3_pre.next

5. 剑指 Offer 52. 两个链表的第一个公共节点


又名浪漫相遇。如果一开始不能走到一起，那就走一走对方走过的路，有缘自会相遇

1
2
3
4
5
6
7
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        node1,node2 = headA,headB
        while(node1 != node2):
            node1 = node1.next if node1 else headB
            node2 = node2.next if node2 else headA
        return node1

6. LeetCode 2. 两数相加


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        pre = ListNode()
        cur = pre
        l1_p = l1
        l2_p = l2
        carry = 0
        while l1_p or l2_p :
            a = l1_p.val if l1_p else 0
            b = l2_p.val if l2_p else 0
            carry,val = divmod(a+b+carry,10)
            cur.next = ListNode(val)
            cur = cur.next
            l1_p = l1_p.next if l1_p else l1_p
            l2_p = l2_p.next if l2_p else l2_p
        if carry:
            cur.next = ListNode(1)
        return pre.next