# Problems of In-place Reversal of Linked List

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
ListNode prev = null;
while (curr != null) {
ListNode oldNext = curr.next;	// 1. stores the old next
curr.next = prev;				// 2. the current points to the previous
prev = curr;					// 3. the current becomes a new previous
curr = oldNext;					// 4. the current moves on
}
return prev;
}
}


Why return prev? Cause prev pointed to the last curr (the last node).

## 92. Reverse Linked List II

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
private ListNode reverseN(ListNode head, int n) {
ListNode prev = null;
for (int i = 0; i < n; i++) {
ListNode oldNext = curr.next;
curr.next = prev;
prev = curr;
curr = oldNext;
}
return prev;
}

public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(42);
ListNode ptr1 = dummy;
ListNode ptr2 = dummy;
// finds the endpoint of the left segment
for (int i = 0; i < m - 1; i++) {
ptr2 = ptr2.next;
}
// finds the endpoint of the right segment
for (int i = 0; i < n + 1; i++) {
ptr1 = ptr1.next;
}
// finds the tail of the reversed linked list
ListNode t = ptr2.next;
// reverses a part of the linked list and gets its head
ListNode h = reverseN(t, n - m + 1);
ptr2.next = h;
// links up the right segment with the tail of the reversed linked list
t.next = ptr1;

return dummy.next;
}
}


Given a singly linked list, determine if it is a palindrome.

We can solve this problem in three steps:

1. finds the middle of the linked list
2. reverses the second half of the linked list
3. traverses from the head and end of the linked list and determines if each of the numbers are equal
/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

ListNode prev = null;
while (curr != null) {
ListNode oldNext = curr.next;
curr.next = prev;
prev = curr;
curr = oldNext;
}
return prev;
}

return true;
}
ListNode ptr1 = reverseList(middle);
while (ptr1 != null && ptr2 != null) {
if (ptr1.val != ptr2.val) {
return false;
}
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
return true;
}
}


## 24. Swap Nodes in Pairs

You may not modify the values in the list’s nodes, only nodes itself may be changed.

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
ListNode dummy = new ListNode(42);
ListNode c = dummy;
while (c.next != null && c.next.next != null) {
ListNode a = c.next;
ListNode b = c.next.next;

// swaps nodes in pair
c.next = b;
a.next = b.next;
b.next = a;

c = c.next.next;
}
return dummy.next;
}
}