|
1 | 1 | package leetcodeEasyLevel; |
2 | 2 |
|
3 | 3 | public class _0234PalindromeLinkedList { |
4 | | - protected ListNode reverse(ListNode head){ |
5 | | - if (head == null || head.next == null) |
6 | | - return head; |
7 | | - ListNode next = reverse(head.next); |
8 | | - head.next.next = head; |
9 | | - head.next = null; |
10 | | - return next; |
| 4 | + // Runtime 2 ms Memory 44.8 MB |
| 5 | + // 리스트가 팰린드롬이면 true를, 아니면 false를 리턴하는 문제이다. |
| 6 | + // 팰린드롬이란? https://sowon-dev.github.io/2021/01/09/210110replacevsreplaceall/ |
| 7 | + // 1->2->2->1 |
| 8 | + |
| 9 | + private ListNode reverse(ListNode head){ |
| 10 | + ListNode preNode = null; |
| 11 | + while(head != null){ |
| 12 | + ListNode nextNode = head.next; |
| 13 | + head.next = preNode; |
| 14 | + preNode = head; |
| 15 | + head = nextNode; |
| 16 | + } |
| 17 | + return preNode; |
11 | 18 | } |
| 19 | + |
12 | 20 | public boolean isPalindrome(ListNode head) { |
13 | | - ListNode fast = head, slow = head; |
| 21 | + // ListNode에 null만 있어도 팰린드롬이다. |
| 22 | + if (head == null || head.next == null) return true; |
14 | 23 |
|
15 | | - while(fast != null && fast.next != null){ |
16 | | - fast = fast.next.next; |
17 | | - slow = slow.next; |
| 24 | + ListNode slow = head; // 1 |
| 25 | + ListNode fast = head; // 1 |
| 26 | + |
| 27 | + while(fast != null && fast.next != null) { // 1!=2 2!=2 null&&null => while종료 |
| 28 | + slow = slow.next; //2 2 |
| 29 | + fast = fast.next.next; //2 null |
18 | 30 | } |
19 | 31 |
|
20 | | - fast = head; |
21 | | - slow = reverse(slow); |
| 32 | + fast = head; // 1 2 2 null |
| 33 | + slow = reverse(slow); //역순으로 1 2 null |
22 | 34 |
|
23 | 35 | while (fast != null && slow != null){ |
24 | 36 | if (fast.val != slow.val) |
|
0 commit comments