LeetCode 初级 链表部分

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

• 示例：
  • 给定一个链表: 1->2->3->4->5, 和 n = 2.
  • 当删除了倒数第二个节点后，链表变为 1->2->3->5.
• 说明：
  • 给定的 n 保证是有效的。
• 进阶：
  • 你能尝试使用一趟扫描实现吗？

解答：

• 思路：
  • 方法： 快慢指针法
    • 快指针指向n个之后的元素，慢指针维持和快指针的间隔为n个元素
  • 边界条件：
    • 初始化的时候快指针就到nullptr了，此时 输入n等于链表的长度，相当于删除链表的第一个节点¹
    • 循环的时候，快指针的next为nullptr，此时快指针指向末尾，慢指针指向 待删除节点的上一个节点。
      • 注意删除倒数第n个节点，和最后节点应该相差n-1个节点的，这里维持的间隔为n个节点，所以慢指针会指向待删除上上一个节点
• Code

  /**
   * Definition for singly-linked list.
   * struct ListNode {
   *     int val;
   *     ListNode *next;
   *     ListNode(int x) : val(x), next(NULL) {}
   * };
   */
  class Solution {
  public:
      ListNode* removeNthFromEnd(ListNode* head, int n) {
          ListNode* first=head;
          while(n--!=0) {first=first->next;}
          if(!first) {return head->next;} // 表示删除第一个
          ListNode* sec=head;
          while(first->next!=NULL){
              sec=sec->next;
              first=first->next;
          }
          sec->next=sec->next->next;
          return head;
      }
  };
  

反转链表

• 反转一个单链表。
• 示例:
  • 输入: 1->2->3->4->5->NULL
  • 输出: 5->4->3->2->1->NULL
• 进阶:
  • 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解答

• 思路1: 递归法
  • 意思阐述:
    • 原来: 1->2->3->NULL
    • 现有: 1->NULL->3->2; 1->2
    • 修改为: 1->next->next=1; 1->next=nullptr
      • 3->2->1->Null
  • 边界条件:
    • 推出条件: head == null || head->next==null
  • Code

  	public ListNode reverseList(ListNode head) {
      ListNode prev = null;
      ListNode curr = head;
      while (curr != null) {
          ListNode nextTemp = curr.next;
          curr.next = prev;
          prev = curr;
          curr = nextTemp;
      }
      return prev;
  	}
  

• 思路2: 迭代法
  • 意思阐述:
    • 新建一个prev==null
    • 然后从head到尾进行迭代,将prev插入到迭代值的next上
  • 边界条件:
    • 当cur==null的时候,此时迭代可以终止了
      • 不是cur->next==null,因为此时cur的val是有效的
    • 返回prev
  • Code

  /**
   * Definition for singly-linked list.
   * struct ListNode {
   *     int val;
   *     ListNode *next;
   *     ListNode(int x) : val(x), next(NULL) {}
   * };
   */
  class Solution {
  public:
      ListNode* reverseList(ListNode* head) {
          ListNode* prev = nullptr;
          ListNode* cur = head;
          while(cur!=nullptr){
              ListNode* nextTemp = cur->next;
              cur->next = prev;
              prev = cur;
              cur = nextTemp;
          }
          return prev;
      }
  };
  

---

1. while(n–)：先判断n是不是0。如果n不为0，n减1，执行循环体。n的变化过程：n-1 ~ 0; while(–n)：n先减1，再判断n是不是0。如果n不为0，执行循环体。n的变化过程：n-1 ~ 1 ↩︎