在LeetCode中看到判断回文的程序:https://leetcode.com/problems/palindrome-linked-list/
里面用单链表来存储数据,先反转前半部分的单链表,然后分别从 表头 和 中间链表位置处 开始比较元素。
反转单链表的代码如下:
1 private ListNode reverseList(ListNode head, int length){
2 if(head == null)
3 return null;
4 ListNode currentNode, preNode;
5 currentNode = preNode = head;
6 ListNode nextNode = head.next;
7 head.next = null;
8 for(int i = 1; i < length; i++){
9 if(nextNode != null){
10 currentNode = nextNode;
11 nextNode = nextNode.next;
12 currentNode.next = preNode;
13 preNode = currentNode;
14 }
15 }
16 return currentNode;
17 }
完整代码如下:
public class ReverseList { public static void main(String[] args) { ListNode head = new ListNode(0); ListNode node1 = new ListNode(1); head.next = node1; ListNode node2 = new ListNode(2); node1.next = node2; ListNode node3 = new ListNode(3); node2.next = node3; print(head); System.out.println(); ListNode newHead = reverseList(head); print(newHead); } public static ListNode reverseList(ListNode head) { if (head == null) { return null; } ListNode currentNode,nextNode,preNode; currentNode = preNode = head; nextNode = head.next; head.next = null; while (nextNode != null) { currentNode = nextNode; nextNode = nextNode.next; //reverse currentNode.next = preNode; preNode = currentNode; } return currentNode; } private static class ListNode{ private int val; private ListNode next; public ListNode(int val) { this.val = val; } } private static void print(ListNode head) { while (head != null) { System.out.print(head.val + " "); head = head.next; } } }