作者：whisper

链接：http://proprogrammar.com:443/article/247

声明：请尊重原作者的劳动，如需转载请注明出处

    在上一章中，我们介绍了如何在链表中使用双指针技巧。本章节中，我们将从如何反转单链表开始并进一步探索更多经典问题。

    反转链表

    让我们从一个经典问题开始：

反转一个单链表。

    一种解决方案是按原始顺序迭代结点，并将它们逐个移动到列表的头部。似乎很难理解。我们先用一个例子来说明我们的算法。

    算法概述

    让我们看一个例子：

    请记住，黑色结点 23 是原始的头结点。

    1. 首先，我们将黑色结点的下一个结点（即结点 6）移动到列表的头部：

    2. 然后，我们将黑色结点的下一个结点（即结点 15）移动到列表的头部：

    3. 黑色结点的下一个结点现在是空。因此，我们停止这一过程并返回新的头结点 15。

    更多

    在该算法中，每个结点只移动一次。

    因此，时间复杂度为 O(N)，其中 N 是链表的长度。我们只使用常量级的额外空间，所以空间复杂度为 O(1)。

    这个问题是你在面试中可能遇到的许多链表问题的基础。如果你仍然遇到困难，我们的下一篇文章将更多地讨论实现细节。

    还有许多其他的解决方案。您应该熟悉至少一个解决方案并能够实现它。

    算法说明

    反转链表

反转一个单链表。

示例:

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

进阶:

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    // 想法：头插法来反转
    public ListNode reverseList(ListNode head) {
        if(head == null){
            return head;
        }
        if(head.next == null)
		{
			return head;
		}

		ListNode newList = head;
		ListNode next = head.next;
		newList.next = null;
		ListNode temp;

		if(next.next != null)
		{
			temp = next.next;
		}
		else
		{
			next.next = newList;
			return next;
		}

		while(temp != null)
		{
			next.next = newList;
			newList = next;
			next = temp;
			temp = temp.next;
		}

		next.next = newList;
		newList = next;

		return newList;
    }

    用到三个指针来翻转，next指向链表当前元素，temp指向链表下个元素，newList指向表头，使当前元素next.next为表头newList，然后通过temp获取下个元素，一次循环后下个元素temp变成当前元素next，重复此操作。

    代码很冗长，繁琐，下面看一个更好的解法

public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

    核心都是使用三个变量进行操作，cur指向当前元素，pre指向新表头，tmp指向下个元素，操作也相同，但十分简洁

    移除链表元素

删除链表中等于给定值 val 的所有节点。

示例:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

// 两个指针，一个指向当前，一个指向前一个结点
    public ListNode removeElements(ListNode head, int val) {
        ListNode cur, pre;
        
        if(head == null){
            return null;
        }
        
        while(head != null && head.val == val){
            head = head.next;
        }
        
        cur = head;
        if(cur != null && cur.next != null){
            pre = cur;
            cur = cur.next;
            
            while(cur != null){
                if(cur.val == val){
                    pre.next = cur.next;
                    cur = cur.next;
                }else{
                    pre = pre.next;
                    cur = cur.next;
                }
                
            }
        }
        
        return head;
    }

    使用双指针pre，cur，当cur是给定val的结点时，利用pre从链表中删除cur，看其它一种解法

public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        while (head !=null && head.val == val) {
            head = head.next;
        }
        ListNode pointer = head;
        while (pointer != null) {
            if (pointer.next != null && pointer.next.val ==val) {
                pointer.next = pointer.next.next;
            } else {
                pointer = pointer.next;
            }
        }
        return head;
    }

    这里只用了一个变量pointer，利用pointer和它的next实现和双指针相同的操作

    奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

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

示例 2:

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

说明:

• 应当保持奇数节点和偶数节点的相对顺序。
• 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    // 想法：node.next.next
    public ListNode oddEvenList(ListNode head) {
        ListNode headEven, even, tempOdd;
        
        if(head == null || head.next == null){
            return head;
        }
        
        tempOdd = head;
        even = head.next;
        headEven = even;
        
        while(even != null && even.next != null){
            tempOdd.next = even.next;
            tempOdd = tempOdd.next;
            
            even.next = tempOdd.next;
            even = even.next;
        }
        
        
        tempOdd.next = headEven;
        return head;
    }
}

    一个链表变成奇数项和偶数项元素的两个链表，再连接这两个链表，再看另一种解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null) return null;
        ListNode odd = head;
        ListNode evenHead = head.next;
        ListNode even = evenHead;
        while(odd.next != null && even.next != null){
            odd.next = odd.next.next;
            odd = odd.next;
            even.next = even.next.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}

    思路差不多，但更加简洁，没有了开始时特殊值处理

    回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    // 想法：先取出val存到列表里，再比较列表中的值
    public boolean isPalindrome(ListNode head) {
        List<Integer> nums = new ArrayList<>();
        
        while(head != null){
            nums.add(head.val);
            head = head.next;
        }
        
        for(int i = 0; i < nums.size() / 2; i++){
            if(!nums.get(i).equals(nums.get(nums.size() - 1 - i))){
                return false;
            }
        }
        
        return true;
    }
}

    先取出val存到列表里，再看列表中的元素是不是回文的，但空间复杂度是O(n)，看一种更好的方法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
        return true;
    }

    if (head.next.next == null) {
        return head.val == head.next.val;
    }

    ListNode fast = head.next;
    ListNode slow = head;

    while (fast.next != null) {
        // 不停的从slow的后一个开始遍历，直到找到值相同的节点
        // 一次完成后，再移动到原节点的下一个节点开始，继续重复上面的步骤
        if (fast.next.val == slow.val) {
            if (fast.next.next != null) {
                return false;
            }
            fast.next = null;
            slow = slow.next;
            fast = slow.next;
            if (fast == null || fast.val == slow.val) {
                return true;
            }
        } else {
            fast = fast.next;
        }
    }
    return false;
}
}

    这里假定链表中相同的元素最多出现两次（在对称的位置出现两次），用了两个指针，慢指针指向当前要比较的元素，快指针寻找其回文对称位置的元素，每次找到后，从链表中丢弃这个元素，这样使每次找到的回文对称位置的元素都是链表的最后一个元素，这样链表不断变短，最终链表中只剩一个元素或两个相同的元素时可以证明是回文链表，这里的空间复杂度是O(1)了，但时间复杂度变成了O(n²)

    小结 - 链表经典问题

    我们为你提供了几个练习。你可能已经注意到它们之间的相似之处了。这里我们提供一些提示：

    1. 通过一些测试用例可以节省您的时间。

    使用链表时不易调试。因此，在编写代码之前，自己尝试几个不同的示例来验证您的算法总是很有用的。

    2. 你可以同时使用多个指针。

    有时，当你为链表问题设计算法时，可能需要同时跟踪多个结点。您应该记住需要跟踪哪些结点，并且可以自由地使用几个不同的结点指针来同时跟踪这些结点。

    如果你使用多个指针，最好为它们指定适当的名称，以防将来必须调试或检查代码。

    3. 在许多情况下，你需要跟踪当前结点的前一个结点。

    你无法追溯单链表中的前一个结点。因此，您不仅要存储当前结点，还要存储前一个结点。这在双链表中是不同的，我们将在后面的章节中介绍。

亲爱的读者：有时间可以点赞评论一下