c++
第一个方法
#include <algorithm>
#include <iostream>
#include <memory>
#include <vector>
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
static void print_list(ListNode* list) {
if (nullptr == list) {
return;
}
ListNode* curr = list;
while (nullptr != curr) {
std::cout << curr->val << " ";
curr = curr->next;
}
std::cout << std::endl;
}
#define PRINT_LOG
class Solution {
public:
// 计算长度
size_t length(ListNode* head) {
if (nullptr == head) {
return 0;
}
size_t length = 0;
auto cursor = head;
while (nullptr != cursor) {
cursor = cursor->next;
length++;
}
return length;
}
// 是否为偶数
template <typename T> bool is_even_number(T num) {
return 0 == (num & 1);
}
bool isPalindrome(ListNode* head) {
// 长度为 0 直接返回 false
auto len = length(head);
if (0 == len) {
return false;
}
// 长度为 1 , 直接返回 true
if (1 == len) {
return true;
}
// 长度为 2 , 直接比较
if (2 == len) {
return head->val == head->next->val;
}
// 长度为 3 , 直接比较
if (3 == len) {
return head->val == head->next->next->val;
}
auto len_is_even = is_even_number(len);
// 找到左边链表尾节点
auto half_len = len / 2;
auto cursor = head;
for (size_t i = 0; i < half_len - 1; i++) {
cursor = cursor->next;
}
auto left_last = len_is_even ? cursor : cursor->next;
// 右边链表起点
ListNode* right_start = left_last->next;
left_last->next = nullptr;
// 构造右边链表
ListNode* right_list = nullptr;
while (nullptr != right_start) {
auto tmp = right_start;
right_start = right_start->next;
if (nullptr == right_list) {
right_list = tmp;
right_list->next = nullptr;
} else {
tmp->next = right_list;
right_list = tmp;
}
}
#ifdef PRINT_LOG
// 打印左右两个链表
std::cout << "分割后的链表" << std::endl;
print_list(head);
print_list(right_list);
#endif
// 比较
bool ret = true;
auto cursor_left = head;
auto cursor_right = right_list;
for (size_t i = 0; i < half_len; i++) {
if (cursor_left->val != cursor_right->val) {
ret = false;
break;
}
cursor_left = cursor_left->next;
cursor_right = cursor_right->next;
}
// 还原链表
cursor_right = right_list;
while (nullptr != cursor_right) {
auto tmp = cursor_right;
cursor_right = cursor_right->next;
tmp->next = left_last->next;
left_last->next = tmp;
}
#ifdef PRINT_LOG
// 打印还原后的链表
std::cout << "还原后的链表:" << std::endl;
print_list(head);
#endif
return ret;
}
};
static void fill_list(ListNode* list, std::vector<int> data) {
ListNode* curr = list;
for (auto i = 0; i < data.size(); i++) {
curr->val = data[i];
if (i < data.size() - 1) {
curr->next = new ListNode();
curr = curr->next;
}
}
}
static void test_even() {
std::cout << "====> test even:" << std::endl;
auto l1 = std::make_unique<ListNode>();
fill_list(l1.get(), {1, 1, 2, 1});
auto solution = std::make_unique<Solution>();
const std::string ret = solution->isPalindrome(l1.get()) ? "Y" : "N";
std::cout << "ret:" << ret << std::endl;
}
static void test_odd() {
std::cout << "====> test odd:" << std::endl;
auto l1 = std::make_unique<ListNode>();
fill_list(l1.get(), {1, 2, 3, 4, 5, 4, 3, 2, 1});
auto solution = std::make_unique<Solution>();
const std::string ret = solution->isPalindrome(l1.get()) ? "Y" : "N";
std::cout << "ret:" << ret << std::endl;
}
int main() {
system("chcp 65001");
test_even();
//test_odd();
std::cout << "Hello World!" << std::endl;
}
java
ListNode.java
package com.laolang.leetcode;
public class ListNode {
public int val;
public ListNode next;
public ListNode() {
}
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
CommonTest.java
package com.laolang.leetcode;
import java.util.List;
import java.util.Objects;
import org.testng.annotations.BeforeClass;
import org.testng.annotations.Test;
import org.testng.collections.Lists;
public class CommonTest {
private Solution solution;
private ListNode list1;
private void fillList(ListNode list, List<Integer> data){
ListNode node = list;
for (int i = 0; i < data.size(); i++) {
node.val = data.get(i);
if( i < data.size() - 1){
node.next = new ListNode();
node = node.next;
}
}
}
@BeforeClass
public void beforeClass(){
solution = new Solution();
list1 = new ListNode();
fillList(list1, Lists.newArrayList(1,2,3,2,1));
}
private void printList(ListNode list){
if(Objects.isNull(list) ){
return ;
}
ListNode curr = list;
while( Objects.nonNull(curr)){
System.out.print(curr.val);
System.out.print(" ");
curr = curr.next;
}
System.out.println();
}
@Test
public void testOne(){
printList(list1);
System.out.println(solution.isPalindrome(list1));
printList(list1);
}
}
第一个方法
package com.laolang.leetcode;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
public class Solution {
public int length(ListNode head) {
if (null == head) {
return 0;
}
int length = 0;
ListNode cursor = head;
while (null != cursor) {
cursor = cursor.next;
length++;
}
return length;
}
public boolean isEventNumber(int num) {
return 0 == (num & 1);
}
public boolean isPalindrome(ListNode head) {
int len = length(head);
// 链表为空, 返回 false
if (0 == len) {
return false;
}
// 链表长度为 1 , 返回 true
if (1 == len) {
return true;
}
// 链表长度为 2 或者 3 , 直接比较
if (2 == len) {
return head.val == head.next.val;
}
if (3 == len) {
return head.val == head.next.next.val;
}
boolean lenIsEven = isEventNumber(len);
// 左边链表尾节点
int halfLen = len / 2;
ListNode cursor = head;
for (int i = 0; i < halfLen - 1; i++) {
cursor = cursor.next;
}
ListNode leftLast = lenIsEven ? cursor : cursor.next;
// 右边链表起点
ListNode rightStart = leftLast.next;
leftLast.next = null;
// 构造右边链表
ListNode rightList = null;
while (null != rightStart) {
ListNode tmp = rightStart;
rightStart = rightStart.next;
if (null == rightList) {
rightList = tmp;
rightList.next = null;
} else {
tmp.next = rightList;
rightList = tmp;
}
}
// 比较
boolean ret = true;
ListNode cursorLeft = head;
ListNode cursortRight = rightList;
for (int i = 0; i < halfLen; i++) {
if (cursorLeft.val != cursortRight.val) {
ret = false;
break;
}
cursorLeft = cursorLeft.next;
cursortRight = cursortRight.next;
}
// 还原链表
cursortRight = rightList;
while (null != cursortRight) {
ListNode tmp = cursortRight;
cursortRight = cursortRight.next;
tmp.next = leftLast.next;
leftLast.next = tmp;
}
return ret;
}
}