链表

1. 反转链表

1.1 递归

  • 时间复杂度 o(N)
  • 空间复杂度 o(N)
  • 装逼利器:happy:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {

    private ListNode successor;//后继节点
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(left==right){
            return head;
        }
        if(left==1){// basecase
            return reverse(head, right);
        }
        if(head != null){
            head.next = reverseBetween(head.next, left-1, right-1);    
        }
        return head;
    }

    public ListNode reverse(ListNode head, int right){
        if(right==1){
            successor = head.next;
            return  head;
        }
        ListNode last = reverse(head.next, right-1);
        head.next.next = head;
        head.next = successor;
        return last;
    }
}

1.2 迭代

2. k个一组反转链表

链表是一种兼具递归和迭代性质的数据结构

反转链表有几种

  • 整个链表反转
  • 部分链表 [a ,b ) 之间反转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null){
            return null;
        }    
        ListNode a, b;
        a = head;
        b = head;
        for(int i=0; i<k; i++){// 求出后继结点
            // basecase
            if(b==null){
                return head;
            }
            b = b.next;
        }
        ListNode newNode = reverse(a, b);
        a.next = reverseKGroup(b, k);
        return newNode;
    }

    /**
    * 反转0-k之间的链表
    * 并且不做后续连接
    * 迭代算法进行翻转
    */
    public ListNode reverse(ListNode left, ListNode right){//left是头结点！反转不包含 right
        ListNode pre, cur, nxt;
        pre = null;
        cur = left;
        nxt = left;
        while(cur != right){
            //后继往后跳
            nxt = cur.next;
            //反转当前节点
            cur.next = pre;
            //更新位置
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
    
}

3. 回文链表

1
2
3
4
5
6
7
8
9
示例一：
    输入: 1->2
    输出: false
    
示例二：
    输入: 1->2->2->1
    输出: true
    
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

借助二叉树后序遍历的思路，不需要显式反转原始链表也可以倒序遍历链表

1
2
3
4
5
6
7
8
// 二叉树遍历方法
void traverse(TreeNode root) {
    // 前序遍历代码
    traverse(root.left);
    // 中序遍历代码
    traverse(root.right);
    // 后序遍历代码
}

同理，链表是二叉树的爹，所以一定也有遍历方法：

1
2
3
4
5
6
//链表遍历方法
void traverse(ListNode head) {
    // 前序遍历代码
    traverse(head.next);
    // 后序遍历代码
}

那么可以知道这道题的解题思路，就是用链表的后序遍历，将值入栈，然后再拿出来与 left 进行对比

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    private ListNode left;
    public boolean isPalindrome(ListNode head) {
       left = head;
       return reverse(head);
    }

    public boolean reverse(ListNode right){
        if(right == null){
            return true;
        }
        boolean result = reverse(right.next);
        result = result && (right.val == left.val);
        left = left.next;
        return result;
    }
}

但是这种方法的时间复杂度 o(N)， 空间复杂度 o(N)，不高效，所以我们来进行一些优化

怎么优化？

像字符串一样，使用快慢指针，并且不使用递归，不使用栈空间，就可以做到空间复杂度 o(N) 啦。

具体如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    private ListNode left;
    public boolean isPalindrome(ListNode head) {
        ListNode slow, fast;
        slow = head;
        fast = head;
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            
        }
        if(fast!=null && fast.next==null){
                slow = slow.next;
            }
        ListNode left = head;
        ListNode right = reverse(slow);
        while(right!=null){
            if(right.val != left.val){
                return false;
            }
            left = left.next;
            right = right.next;
        }
        return true;
    }
    public ListNode reverse(ListNode head){
        ListNode pre, nxt, cur;
        pre = null;
        cur = head;
        nxt = head;
        while(cur != null){
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}