• 寻找回文串 –> 双指针从两端向中间逼近

  • 寻找一个字符串中最大回文串 –> 寻找以s[left]和s[right]为中心的最长回文串 （中间向两端逼近）

判断回文单链表

思路1：将单链表的值放到数组中，然后通过数组来判断

思路2：反转单链表，判断两个链表是否完全相同

思路3：利用二叉树后序遍历思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode left=null;
public boolean isPalindrome(ListNode head) {
    // 方法1：将单链表反转成新的链表
    // 方法2：将单链表的值放到数组中，通过数组来判断
    // 方法3：利用二叉树后续遍历思路
    left=head;
    return traverse(head);
}

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

思路4：优化空间复杂度

  • 先找到链表的中点 使用快慢指针
  • 反转后半部分链表 
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
public boolean isPalindrome(ListNode head) {
    // 方法1：将单链表反转成新的链表
    // 方法2：将单链表的值放到数组中，通过数组来判断
    // 方法3：利用二叉树后续遍历思路
    // 方法4：寻找链表的中间结点，将链表的后半段翻转
    ListNode slow=head; ListNode fast=head;
    while(fast!=null && fast.next!=null){
        slow=slow.next;
        fast=fast.next.next;
    }
    if(fast!=null){  //链表的结点个数是奇数
        slow=slow.next;
    }
    ListNode right=reverse(slow);
    ListNode left=head;
    while(right!=null){
        if(left.val!=right.val){
            return false;
        }
        left=left.next;
        right=right.next;
    }
    return true;
}
public ListNode reverse(ListNode slow){
    ListNode pre=null;
    ListNode cur=slow;
    while(cur!=null){
        ListNode s=cur.next;
        cur.next=pre;
        pre=cur;
        cur=s;
    }
    return pre;
}

反转链表

如何反转单链表？ 剑指 Offer 24. 反转链表

  1. 依靠栈

  2. 头插法，把原链表一个一个摘下，插入到新链表前面

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public ListNode ReverseList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode p=head.next;
        ListNode pre=head;
        pre.next=null;
        while(p!=null){
            ListNode s=p;
            p=p.next;
            s.next=pre;
            pre=s;
        }
        return pre;
    }

  3. 递归

递归的空间复杂度为O(N),而迭代的时间复杂度为O(1).

递归反转整个链表

==递归最重要的就是明确递归函数的含义==

ListNode reverse(ListNode head) // 输入单链表头结点，将该头结点的整个链表反转，返回新的头结点

image-20220925112218962

1
2
3
4
5
6
7
8
9
public ListNode ReverseList(ListNode head) {
    if(head==null || head.next==null){
        return head;
    }
    ListNode last=ReverseList(head.next);
    head.next.next=head;
    head.next=null;
    return last;
}

递归方式，代码简洁优雅

递归反转部分链表

92. 反转链表 II

reverseBetween(ListNode head, int left, int right) //输入单链表头结点，将链表的第left结点到第right结点反转，返回新链表的头结点

首先，考虑如何反转前n个结点

image-20220925115211597

1
2
3
4
5
6
7
8
9
10
11
ListNode successor=null; 
public ListNode reverseN(ListNode head，int n) {
    if(n==1){
        successor=head.next;
        return head;
    }
    ListNode last=reverseN(head.next,n-1);
    head.next.next=head;
    head.next=successor;
    return last;
}

解决：递归反转部分链表

left=1 就想当于反转前n个结点

left!=1 前进到反转的起点

1
2
3
4
5
6
7
public ListNode reverseBetween(ListNode head, int left, int right) {
    if(left==1){
        return reverseN(head,right);
    }
    head.next=reverseBetween(head.next,left-1,right-1);
    return head;
}

k个一组反转链表

递归解决

image-20220927102415994