2022-5-15 链表(2022-5-15 linked list)

234. 回文链表

给你一个单链表的头节点  ，请你判断该链表是否为回文链表。如果是，返回  ；否则，返回  。

head
true
false
 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode() {}
 7  *     ListNode(int val) { this.val = val; }
 8  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 9  * }
10  */
11 class Solution {
12     public boolean isPalindrome(ListNode head) {
13         StringBuilder sb=new StringBuilder();
14         ListNode point=head;
15         while (point!=null){
16             sb.append(point.val);
17             point=point.next;
18         }
19         ListNode pre=null,cur=head,next=head;
20         while (cur!=null){
21             next=cur.next;
22             cur.next=pre;
23             pre=cur;
24             cur=next;
25         }
26         StringBuilder sb1=new StringBuilder();
27         point=pre;
28         while (point!=null){
29             sb1.append(point.val);
30             point=point.next;
31         }
32         if (sb.toString().equals(sb1.toString()))  return true;
33         return false;
34     }
35 }

思路：反转链表判断，但是占用空间不是1。快慢指针找到中点，再反转后面比较，可以占用1空间。

————————

234. Palindrome linked list

Give you the head node of a single linked list. Please judge whether the linked list is a palindrome linked list. If yes, return; Otherwise, return.

head
true
false
 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode() {}
 7  *     ListNode(int val) { this.val = val; }
 8  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 9  * }
10  */
11 class Solution {
12     public boolean isPalindrome(ListNode head) {
13         StringBuilder sb=new StringBuilder();
14         ListNode point=head;
15         while (point!=null){
16             sb.append(point.val);
17             point=point.next;
18         }
19         ListNode pre=null,cur=head,next=head;
20         while (cur!=null){
21             next=cur.next;
22             cur.next=pre;
23             pre=cur;
24             cur=next;
25         }
26         StringBuilder sb1=new StringBuilder();
27         point=pre;
28         while (point!=null){
29             sb1.append(point.val);
30             point=point.next;
31         }
32         if (sb.toString().equals(sb1.toString()))  return true;
33         return false;
34     }
35 }

< strong > idea: reverse the linked list judgment, but the occupied space is not 1. The speed pointer finds the midpoint, and then reverses the later comparison, which can occupy 1 space