Leetcode日记：19&24&84.链表相关操作

19.删除倒数第N个元素

19-题目

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

19-题目分析

首先，题目要求删除链表中倒数第n个元素。
其实很简单，我们只需要遍历一遍链表，知道链表的元素个数。再次遍历，找到length-n个元素就可以了。
但是题目有进阶要求，能不能只遍历一次？

答案是肯定的。请看下面代码：

19-代码

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode start = new ListNode(0);
    ListNode slow = start, fast = start;
    slow.next = head;
    //Move fast in front so that the gap between slow and fast becomes n
    for(int i=1; i<=n+1; i++)   {
        fast = fast.next;
    }
    //Move fast to the end, maintaining the gap
    while(fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
    //Skip the desired node
    slow.next = slow.next.next;
    return start.next;
}

19-代码分析

这里用到了一个很巧妙的方法，我将它命名为“双指针分离法”，主要思想就是先让这两个指针岔开n个元素，然后两个指针同时向前步进。当前面的元素到最后时，后面那个元素刚好指向倒数第n个元素。
算法示意图：

leetcode19.png

24.成对交换节点

24-题目

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

24-题目分析

结点交换，是链表中老生常谈的一个话题，看似简单，编写程序的时候，容易被节点绕晕，那么我们就看看这个程序时如何编写的吧！

24-代码

public ListNode swapPairs(ListNode head) {
    if ((head == null)||(head.next == null))
        return head;
    ListNode n = head.next;
    head.next = swapPairs(head.next.next);
    n.next = head;
    return n;
}

24-代码分析

这里采用了递归，是因为如果从前往后交换的话，前面一对链接的一定要是已经交换好的下一对，所以程序的运行顺序是先将最后的交换好，然后逐渐往回过渡。

leetcode24.jpg

如图所示，每一层递归，我们都会创建new一个新节点，这个节点首先保存为head.next的信息，然后进行递归，递归返回输入链表的交换后的头节点，随后将返回的头节点设置为head.next。最后，将n.next指向head完成交换，此时原来的head.next完全被隔离，被系统回收。

这道题看似容易，实际上还是需要一番思考的。

82.删除链表重复元素II

82-题目

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:

Input: 1->1->1->2->3
Output: 2->3

82-题目分析

之前有一道题是保留一个重复元素，删除多余的，那道题比较简单，这道题的意图是：只要是重复的元素，都删除，一个不留。
这就牵扯到，你要有两个指针，一个指针用于记录上一个不重复元素，另一个指针负责向前步进检测并删除重复元素。

82-代码

public ListNode deleteDuplicates(ListNode head) {
    if(head==null) return null;
    ListNode FakeHead=new ListNode(0);
    FakeHead.next=head;
    ListNode pre=FakeHead;
    ListNode cur=head;
    while(cur!=null){
        while(cur.next!=null&&cur.val==cur.next.val){
            cur=cur.next;
        }
        if(pre.next==cur){
            pre=pre.next;
        }
        else{
            pre.next=cur.next;
        }
        cur=cur.next;
    }
    return FakeHead.next;
}

82-代码分析

从代码中我们可以看出，代码用了两个指针，第一个指针pre用来记录最后一个不重复的指针（这个指针一定不会被删除掉）。第二个指针cur用来记录当前位置，用它来判断是否该元素为重复元素(cur.next!=null&&cur.val==cur.next.val)，利用一个循环，直接找到下一个出现的不重复元素，这里有两种情况，一种是循环没有被执行（即cur为一个不重复元素），那么cur没有移动，我们让pre=pre.next，来更新最后一个不重复元素。如果是重复元素，则跨过cur，执行pre.next=cur.next。

链表问题总结

链表问题在所有数据结构里面所示较为简单的一种。而且相对来说问题的变数比较少，我们着重关注以下几个问题

1. dummy哑节点

   我们可以看到，上面题目中，第一题的
   ListNode start = new ListNode(0);
   最后一道题的
   ListNode FakeHead=new ListNode(0);
   都首先创建了一个新节点，这个结点的下一个往往是输入的头节点，为什么会这么设置呢？
   哑节点设置的主要原因：
   避免头节点可能由于某种原因被删除等一系列问题而导致的边界问题，简化代码。

2. 双指针设计

   链表的很多问题用双指针都会降低一些时间复杂度。比如leetcode24等很多问题可以应用在很多场景中：

   • 删除链表中元素
   • 拆分链表
   • 找出中点或中位数
   • 寻找链表是否存在环
   • 寻找范围

   还有更多应用，但是思想都是不变的，指针一快一慢，具体快多少，看题目中具体要求。这便是著名的“快慢指针”

更多关于链表的问题

更多关于回溯算法的问题请转到链表标签