链表系列题目合集：Leetcode链表题目
建议先看本人博客中算法通关面试40讲中的链表部分题目。
方法：

• 使用prev前置指针，用于反转链表全部或部分类的题目
• 使用快慢指针，用于判断链表内部是否有环类题目，以及删除节点题目
• 环形问题找到环的入口方法：快慢指针第一次相遇后，快指针从头部再与慢指针相遇的位置
• 获得链表的中间节点，使用快慢指针，快指针走两步，慢指针走一步，快指针next为null或者为null时，慢指针指向中间节点
• 双指针连接链表法，用于查找相交链表

Leetcode-23. 合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

解法：1. 暴力算法，将所有节点放在一个数组中，排序之后输出，时间O(NlogN)，N是节点总数。2. 分治，将k个list两两组合，用图来表示如下，时间复杂度O(NlogK)，k是链表的条数，空间复杂度O（1）

• Java

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
   
    public ListNode mergeKLists(ListNode[] lists) {
   
        if (lists==null || lists.length==0) return null;
        int amount = lists.length;
        int i = 1;
        while (i < amount) {
   
            for (int j=0;j+i<amount;j += i*2) {
   
                lists[j] = this.mergeTwoLists(lists[j], lists[j+i]);
            }
            i *= 2;
        }
        return lists[0];
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
   
        ListNode pointer = new ListNode(0);
        ListNode head = pointer;
        while (l1!=null && l2!=null) {
   
            if (l1.val > l2.val) {
   
                pointer.next = l2;
                l2 = l2.next;
            } else {
   
                pointer.next = l1;
                l1 = l1.next;
            }
            pointer = pointer.next;
        }
        if (l1==null) {
   
            pointer.next = l2;
        } else {
   
            pointer.next = l1;
        }
        return head.next;
    }
}

• Python

class Solution(object):
    def mergeKLists(self, lists):
        """ :type lists: List[ListNode] :rtype: ListNode """
        amount = len(lists)
        interval = 1
        while interval < amount:
            for i in range(0, amount - interval, interval * 2):
                lists[i] = self.merge2Lists(lists[i], lists[i + interval])
            interval *= 2
        return lists[0] if amount > 0 else lists

    def merge2Lists(self, l1, l2):
        head = point = ListNode(0)
        while l1 and l2:
            if l1.val <= l2.val:
                point.next = l1
                l1 = l1.next
            else:
                point.next = l2
                l2 = l1
                l1 = point.next.next
            point = point.next
        if not l1:
            point.next=l2
        else:
            point.next=l1
        return head.next

Leetcode-82. 删除排序链表中的重复元素 II

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:

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

解法：只要节点的左右值不同，那么节点就是一个可用节点，否则不是

• Java

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
   
    public ListNode deleteDuplicates(ListNode head) {
   
        if (head == null) return head;
        ListNode pointer = new ListNode(0==head.val? 1: 0);
        ListNode pre = pointer, l = pointer;
        while (head != null) {
   
            while (head!=null && (pre.val==head.val || (head.next!=null && head.val==head.next.val))) {
   
                pre = head;
                head = head.next;
            }
            pointer.next = head;
            pointer = pointer.next;
            pre = head;
            head = head==null? head: head.next;
        }
        return l.next;
    }
}

Leetcode-61. 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 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

解法：很简单，找到rotate的位置和null前的位置，进行rotate即可

• Java

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
   
    public ListNode rotateRight(ListNode head, int k) {
   
        if (head == null) return null;
        
        int length = 1;
        ListNode tmp = head, pre = tmp, cur = tmp;
        while (tmp.next != null) {
    //Get the total length 
            tmp = tmp.next;
            length++;
        }
        
        k = k%length;
        if (k==0) return head;
        
        for (int i=0;i<length-k-1;i++) {
    //Get the length-k%length th node
            pre = pre.next;
        }
        cur = pre.next; // rotate
        pre.next = null;
        tmp.next = head;
        return cur;
    }
}

Leetcode-86. 分隔链表

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

解法：用两个链表分别存储小于x的和不小于的，最后连接一下就可以

• Java

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
   
    public ListNode partition(ListNode head, int x) {
   
        ListNode pre = new ListNode(0);
        ListNode after = new ListNode(0);
        ListNode dummy1 = pre;
        ListNode dummy2 = after;
        while (head !=null) {
   
            if (head.val<x) {
   
                pre.next = head;
                pre = pre.next;
            } else{
   
                after.next = head;
                after = after.next;
            }
            head = head.next;
        }
        after.next = null;
        pre.next = dummy2.next;
        return dummy1.next;
    }
}

Leetcode-92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

解法：我这里采用的办法是分开再连接，将要进行反转的部分拆出来，利用了头尾节点在翻转中的被调转过来的特性。这道题可以打个星号着重看一下，时间复杂度O（N），空间复杂度O（1）。

• Java

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
   
    public ListNode reverseBetween(ListNode head, int m, int n) {
   
        if (head==null || head.next==null) return head;
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode dummy = pre;
        ListNode cur = head; 
        // 想要将pre移至m的前一个节点，cur移至n节点上，现在pre和cur相差1节点，达到目的时相差n-m+1节点，所以cur需要移动n-m个节点才能保持两者间距为n-m+1
        for (int i=0;i<n-m;i++) {
   
            cur = cur.next;
        }
        // 同时平移至目标位置
        for (int i=0;i<m-1;i++) {
   
            pre = pre.next;
            cur = cur.next;
        }
        // 记录下pre当前的位置
        ListNode node = pre;
        // 记录cur的下一个位置，因为reverse之后还要连接回去
        ListNode next = cur.next;
        cur.next = null;
        // 将pre调整到下一个节点进行翻转，传入的头尾节点是pre和cur，翻转之后的头尾节点是cur和pre，再进行重新连接即可
        pre = pre.next;
        // node.next = this.reverseList(pre); // 与node.next = cur是一个效果
        this.reverseList(pre);
        // 重新连接
        node.next = cur;
        pre.next = next;
        return dummy.next;
    }
    public ListNode reverseList(ListNode head) {
   
        ListNode pre = null;
        while (head != null) {
   
            ListNode tmp = head.next;
            head.next = pre;
            pre = head;
            head = tmp;
        }
        return pre;
    }
}

Leetcode-108.将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

解法：利用中间节点使用递归，

• Java

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
   
    public TreeNode sortedArrayToBST(int[] nums) {
   
        if (nums==null || nums.length==0) return null;
        return this.helper(nums, 0, nums.length-1);
    }
    public TreeNode helper(int[] nums, int left, int right) {
   
        int mid = (left+right) / 2;
        TreeNode p = new TreeNode(nums[mid]);
        if (mid != left) {
   
            p.left = this.helper(nums, left, mid-1);
        }
        if (mid != right) {
   
            p.right = this.helper(nums, mid+1, right);
        }
        return p;
    }
}

Leetcode-109. 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

解法：1. 使用链表的快慢指针找到中间元素，然后将中间元素作为root，左边右边分别使用递归变为二叉搜索树，最终返回root即可，时间复杂度O(NlogN)，空间复杂度O(logN)。2. 与上面的方法类似，不过是将链表转换成数组在进行操作，时间复杂度O(N)，空间复杂度O(N）

• Java
  链表

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
   

  private ListNode findMiddleElement(ListNode head) {
   
    ListNode prevPtr = head;
    ListNode slowPtr = prevPtr;
    ListNode fastPtr = prevPtr;
    while (fastPtr != null && fastPtr.next != null) {
   
      prevPtr = slowPtr;
      slowPtr = slowPtr.next;
      fastPtr = fastPtr.next.next;
    }
      prevPtr.next = null;
    return slowPtr;
  }

  public TreeNode sortedListToBST(ListNode head) {
   

    if (head == null) {
   
      return null;
    }
    ListNode mid = this.findMiddleElement(head);
    TreeNode node = new TreeNode(mid.val);
    if (head == mid) {
   
      return node;
    }
    node.left = this.sortedListToBST(head);
    node.right = this.sortedListToBST(mid.next);
    return node;
  }
}

数组

class Solution {
   
    public TreeNode sortedListToBST(ListNode head) {
   
        if (head==null) return null;
        ArrayList<Integer> lst = new ArrayList<Integer>();
        lst = this.addList(head, lst);
        return this.helper(lst, 0, lst.size()-1);
    }
    public ArrayList<Integer> addList(ListNode head, ArrayList<Integer> lst) {
   
        ListNode tmp = head;
        while (tmp != null) {
   
            lst.add(tmp.val);
            tmp = tmp.next;
        }
        return lst;
    }
    public TreeNode helper(ArrayList<Integer> lst, int left, int right) {
   
        int mid = left + (right-left)/2;
        TreeNode root = new TreeNode(lst.get(mid));
        if (mid != left) {
   
            root.left = this.helper(lst, left, mid-1);
        }
        if (mid != right) {
   
            root.right = this.helper(lst, mid+1, right);
        }
        return root;
    }
}

Leetcode-138. 复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。

输入：
{“KaTeX parse error: Expected '}', got 'EOF' at end of input: …":"1","next":{"id”:“2”,“next”:null,“random”:{“KaTeX parse error: Expected 'EOF', got '}' at position 9: ref":"2"}̲,"val":2},"rand…ref”:“2”},“val”:1}

解释：
节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。

提示：

你必须返回给定头的拷贝作为对克隆列表的引用。

解法：深拷贝，要建立额外的node来进行保存，使用map判断对应的node是否之前建立过（因为有random），时间复杂度O(N)，空间复杂度O(N)

• Java

/* // Definition for a Node. class Node { public int val; public Node next; public Node random; public Node() {} public Node(int _val,Node _next,Node _random) { val = _val; next = _next; random = _random; } }; */
class Solution {
   
    HashMap<Node, Node> visited = new HashMap<>();
    public Node copyRandomList(Node head) {
   
        if (head==null) return null;
        Node oldNode = head;
        Node newNode = new Node(oldNode.val, null, null);
        this.visited.put(oldNode, newNode);
        while (oldNode != null) {
   
            newNode.next = this.getNode(oldNode.next);
            newNode.random = this.getNode(oldNode.random);
            oldNode = oldNode.next;
            newNode = newNode.next;
        }
        return this.visited.get(head);
    }
    public Node getNode(Node node) {
   
        if (node==null) return null;
        if (this.visited.containsKey(node)) {
   
            return this.visited.get(node);
        } else {
   
            this.visited.put(node, new Node(node.val, null, null));
            return this.visited.get(node);
        }
    }
}

Leetcode-143. 重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

解法：1. 先从中间拆开，翻转后面的，在挨个插入前面的。2. 每次都把最后一个元素放在第一个元素后面

递归挨个插入

• Java

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
   
    public void reorderList(ListNode head) {
   
        if (head==null) return;
        ListNode slow = head;
        ListNode fast = slow;
        ListNode pre = slow;
        while (fast!=null && fast.next!=null) {
   
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        
        ListNode l1 = head;
        ListNode l2 = null; // 翻转后的头部
        while (slow!=null) {
   
            ListNode tmp = slow.next;
            slow.next = l2;
            l2 = slow;
            slow = tmp;
        }
        head = this.reorder(l1, l2);
    }
    public ListNode reorder(ListNode head1, ListNode head2) {
   
        if (head1==null && head2==null) {
   
            return null;
        } else if (head1 == null) {
   
            return head2;
        } else {
   
        ListNode next1 = head1.next;
        ListNode next2 = head2.next;
        ListNode dummy = head1;
        head1.next = head2;
        head2.next = this.reorder(next1, next2);
        return dummy;
        }
    }
}

class Solution {
   
    public void reorderList(ListNode head) {
   
		// Nothing to do if the list has 2 or fewer nodes
        if (head == null || head.next == null || head.next.next == null) return;

        ListNode slast = head; // second last node
        ListNode last = head.next; // last node
        
        while (last.next != null) {
   
            last = last.next;
            slast = slast.next;
        }
        
		// Insert the last node right after the first node
        ListNode tmp = head.next;
        head.next = last;
        last.next = tmp;
		
		// Second last node should point to null otherwise there would be a cycle
		slast.next = null;
        
        reorderList(tmp);
    }
}

Leetcode-147. 对链表进行插入排序

对链表进行插入排序。
在这里插入图片描述

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
3. 重复直到所有输入数据插入完为止。

示例 1：

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

示例 2：

输入: -1->5->3->4->0
输出: -1->0->3->4->5

解法：此题考察的是插入算法，每次链表的左边都保持有序，在右边遍历元素插入左边的合适的位置，时间复杂度O(N)，空间复杂度O(N)

• Java

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
   
    public ListNode insertionSortList(ListNode head) {
   
        if (head==null || head.next==null) return head;
        ListNode pre = new ListNode(head.val);
        ListNode l ;
        head = head.next;
        while (head != null) {
   
            ListNode next = head.next;
            head.next = null;
            pre = this.insertNode(pre, head);
            head = next;
        }
        return pre;
    }
    public ListNode insertNode(ListNode head, ListNode node) {
   
        if (head == null) {
   
            head = node;
            return head;
        }
        // 设置两个tmp是为了不改变head和node的结构
        ListNode tmp1 = head;
        ListNode tmp2 = node;
        ListNode pre = new ListNode(0);
        pre.next = tmp1;
        ListNode dummy = pre;
        while (tmp1 != null) {
   
            // 如果大于插入值的位置立马插入，并返回
            if (tmp1.val > tmp2.val) {
   
                ListNode next = tmp1.next;
                pre.next = tmp2;
                tmp2.next = tmp1;
                tmp1 = next;
                return dummy.next;
            } else{
   
                // 没找到的话继续向下找
                pre = tmp1;
                tmp1 = tmp1.next;
            }
        }
        // 如果到了最后还没有找到，说明插入的节点的值是最大的，插入到最后
        pre.next = node;
        node.next = null;
        return dummy.next;
    }
}

Leetcode-148. 排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4
示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

解法：由O(NlogN)联想到可能是归并排序（merge sort），使用递归即可。

• Java

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
   
    public ListNode sortList(ListNode head) {
   
        if (head==null || head.next==null) return head;
        ListNode pre = head;
        ListNode slow = head;
        ListNode fast = head;
        while (fast!=null && fast.next!=null) {
   
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        ListNode l1 = this.sortList(head);
        ListNode l2 = this.sortList(slow);
        return this.mergeTwoList(l1, l2);
    }
    public ListNode mergeTwoList(ListNode l1, ListNode l2) {
   
        if (l1==null || l2==null) {
   
            return l1==null?l2:l1;
        }
        ListNode pointer = new ListNode(0);
        ListNode dummy = pointer;
        while (l1!=null && l2!=null) {
   
            if (l1.val<l2.val) {
   
                pointer.next = l1;
                l1 = l1.next;
            } else {
   
                pointer.next = l2;
                l2 = l2.next;
            }
            pointer = pointer.next;
        }
        if (l1==null) {
   
            pointer.next = l2;
        } else {
   
            pointer.next = l1;
        }
        return dummy.next;
    }
}

Leetcode-160. 相交链表

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

• 如果两个链表没有交点，返回 null.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

解法：1. 使用set添加第一条链路的元素，然后在第二个链路中查找有无，时间复杂度O(M+N)，空间复杂度O(M) 2. 双指针法。创建两个指针 pA 和 pB，分别初始化为链表 A 和 B 的头结点。然后让它们向后逐结点遍历。当 pA到达链表的尾部时，将它重定位到链表 B 的头结点 (你没看错，就是链表 B); 类似的，当 pB到达链表的尾部时，将它重定位到链表 A 的头结点。若在某一时刻 pApA 和 pBpB 相遇，则 pA/pB为相交结点。时间复杂度O(M+N)，空间复杂度O(1)

• Java
  使用Set

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
   
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
   
        if (headA==null || headB==null) {
   
            return null;
        } 
        Set<ListNode> set = new HashSet<>();
        ListNode l1 = headA;
        ListNode l2 = headB;
        while (l1 != null) {
   
            set.add(l1);
            l1 = l1.next;
        }
        while (l2 != null) {
   
            if (set.contains(l2)) return l2;
            l2 = l2.next;
        }
        return null;
    }
}

使用双指针法

public class Solution {
   
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
   
        ListNode ha = headA, hb = headB;
        while (ha != hb) {
   
            ha = ha != null ? ha.next : headB;
            hb = hb != null ? hb.next : headA;
        }
        return ha;
    }
}

Leetcode-203. 移除链表元素

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

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

解法：相等就跳过，非常简单的题

• Java

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
   
    public ListNode removeElements(ListNode head, int val) {
   
        if (head==null) return null;
        ListNode l1 = new ListNode(0==val?-1:0);
        l1.next = head;
        ListNode l2 = l1;
        ListNode dummy = l1;
        while (l1 != null) {
   
            if (l1.val != val) {
   
                l2 = l1;
                l1 = l1.next;
            } else {
   
                ListNode tmp = l1.next;
                l2.next = tmp;
                l1 = tmp;
            }
        }
        return dummy.next;
    }
}

Leetcode-234. 回文链表

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

示例 1:

输入: 1->2
输出: false

示例 2:

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

进阶：

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

解法：使用快慢指针找到中点，将后半条链表翻转再与前半条链表一一比较，时间复杂度O(N)

• Java

/** * 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 || head.next==null) return head;
        ListNode l1 = head;
        ListNode pre = null;
        while (l1!=null) {
   
            ListNode tmp = l1.next;
            l1.next = pre;
            pre = l1;
            l1 = tmp;
        }
        return pre;
    }
    public boolean isPalindrome(ListNode head) {
   
        if (head==null || head.next==null) return true;
        ListNode pre = head;
        ListNode slow = pre;
        ListNode fast = pre;
        ListNode head1 = pre;
        while (fast!=null && fast.next!=null) {
   
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        ListNode head2 = this.reverseList(slow);
        while (head1 != null && head2!=null) {
   
            if (head1.val != head2.val) return false;
            head1 = head1.next;
            head2 = head2.next;
        }
        return true;
    }
}

Leetcode-328. 奇偶链表

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

请尝试使用原地算法完成。你的算法的空间复杂度应为 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

说明:

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

解法：分别记录奇偶节点，奇节点连接在一起，偶节点连接在一起，最后将偶链表连接在奇链表之后，时间复杂度O(N)，空间复杂度O(1)

• Java

/** * 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 || head.next==null) return head;
        ListNode odd = head;
        ListNode evenHead = head.next;
        ListNode even = evenHead;
        while (even!=null && even.next!=null) {
   
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}