2. 链表操作

Q2. 两数相加 MEDIUM

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例：

  1. 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
  2. 输出：7 -> 0 -> 8
  3. 原因：342 + 465 = 807
  5. 通过次数426,173        |        提交次数1,138,856
  1. class Solution:
  2.     def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
  3.         new_l = ListNode(0)
  4.         p = new_l
  5.         flag = 0
  6.         while l1 or l2 :
  7.             a = l1.val if l1 else 0
  8.             b = l2.val if l2 else 0
  9.             flag = a+b+flag
  10.             p.next = ListNode(flag%10)
  11.             p = p.next
  12.             flag = 0 if flag < 10 else 1
  13.             if l1:
  14.                 l1 =l1.next
  15.             if l2:
  16.                 l2 = l2.next
  17.         if flag:
  18.             p.next = ListNode(1)
  19.         return new_l.next
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *res = new ListNode(0);
        ListNode *p = res;
        int flag = 0;
        while (l1 || l2)
        {
            int a = l1?l1->val:0;
            int b = l2?l2->val:0;
            flag = a+b+flag;
            p->next = new ListNode(flag%10);
            p = p->next;
            flag = flag/10;
            l1 = l1?l1->next:nullptr;
            l2 =l2?l2->next:nullptr;
        }
        if (flag) p->next = new ListNode(1);
        return res->next;
    }
};

Q19. 删除链表的倒数第N个节点 MEDIUM

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明:给定的 *n* 保证是有效的。
进阶：你能尝试使用一趟扫描实现吗？

通过次数171,723        |        提交次数444,661

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        pre = ListNode('')
        pre.next = head
           low,fast = pre,pre
        for i in range(n):
            fast = fast.next
        while fast.next:
            fast = fast.next
            low = low.next
        low.next = low.next.next
        return pre.next

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     采用两个间隔为n的指针，同时向前移动。
     当快指针的下一个节点为最后一个节点时，要删除的节点就是慢指针的下一个节点。
     */
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // write code here
        if(!head||!head->next) return {};
        ListNode *fast = head,*low=head;
        for(int i =0;i<n;i++)
        {
            fast =fast->next;
        }
        if (!fast) return head->next;// 删除第一个节点
        while(fast->next)
        {
            fast = fast->next;
            low = low->next;
        }
        low ->next = low->next->next;
        return head;
    }
};

Q61. 旋转链表 MEDIUM

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。 示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
**解释:**
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
**解释:**
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

通过次数62,094        |        提交次数154,304

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not k :
            return head
        p,l = head,1
        while p.next:
            p,l = p.next,l+1
        p.next = head#头尾相接
        k = l - k%l-1
        while k > 0:
            head,k = head.next,k-1
        res,head.next = head.next,None#新头 断循环
        return res

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* rotateRight(ListNode* head, int k) {
        // write code here
        if(!head || k ==0) return head;
        ListNode* p = head;
        int length =1;
        while (p->next)
        {
            p = p->next;
            length++;
        }
        p->next = head;
        k = length - k%length -1;
        while(k>0)
        {
            head = head->next;
            k--;
        }
        ListNode* res= head->next;
        head->next = nullptr;
        return res;

    }
};

Q138. 复制带随机指针的链表 MEDIUM

Q206. 反转链表 EASY

反转一个单链表。 示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

通过次数241,857        |        提交次数350,164

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        #迭代
        new = None
        while head:
            p = head
            head = p.next
            p.next = new
            new = p
        return new
class Solution:
    '''
        原链表的头结点就是反转之后链表的尾结点，使用 headhead 标记 .
        定义指针 curcur，初始化为 headhead .
        每次都让 headhead 下一个结点的 nextnext 指向 curcur ，实现一次局部反转
        局部反转完成之后，curcur 和 headhead 的 nextnext 指针同时 往前移动一个位置
        循环上述过程，直至 curcur 到达链表的最后一个结点 .
    '''
    def reverseList(self, head: ListNode) -> ListNode:
        #递归
        if not head or not head.next:
            return head
        p = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return p