快慢指针+栈
用快慢指针找到中点,顺便存下slow(也就是存下前半段链表),然后利用栈先进后出的特性,直接处理
/**
* 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; }
* }
*/
class Solution {
public int pairSum(ListNode head) {
if(head.next.next == null) return head.val + head.next.val;
ListNode slow = head, fast = head.next;
Deque<ListNode> deque = new LinkedList<>();
deque.addFirst(slow);
while(fast.next != null) {
slow = slow.next;
deque.addFirst(slow);
fast = fast.next.next;
}
int res = 0;
slow = slow.next;
while(!deque.isEmpty()) {
res = Math.max(res, deque.removeFirst().val + slow.val);
slow = slow.next;
}
return res;
}
}
快慢指针+反转链表
先用快慢指针找到中点,然后断开链表,把前半段链表反转
/**
* 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; }
* }
*/
class Solution {
public int pairSum(ListNode head) {
if(head.next.next == null) return head.val + head.next.val;
ListNode slow = head, fast = head.next;
while(fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode rear = slow.next;
slow.next = null;
ListNode pre = reverseList(head);
int res = 0;
while(rear!= null) {
res = Math.max(res, pre.val + rear.val);
pre = pre.next;
rear = rear.next;
}
return res;
}
ListNode reverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode rear = reverseList(head.next);
head.next.next = head;
head.next = null;
return rear;
}
}
递归
递归到最后一个然后和第一个相加,倒数第二个跟第二个,以此类推
/**
* 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; }
* }
*/
class Solution {
int res = 0;
ListNode first;
public int pairSum(ListNode head) {
first = head;
dfs(head);
return res;
}
boolean dfs(ListNode head) {
if(head == null) return true;
if(!dfs(head.next)) return false;
res = Math.max(res, head.val + first.val);
first = first.next;
return true;
}
}