Unit 1 Practice I
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.
//Definition for singly-linked list.
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
图示如下：
- Delete Node in Linked List
Unit 2 Practice II
Reverse a singly linked list.
Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?
(1) Reverse the linked list iteratively
- reverseLinkedlist.jpg
// Definition for singly-linked list.
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode reverseList(ListNode head) {
if (head == null ||head.next == null) {
return head;
}
ListNode pre = head;
ListNode cur = pre.next;
head.next = null;
while (pre != null && cur != null) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
(2) Reverse the linked list recursively
-
ReverseLinkedlistRecursively.jpg
举例说明：反转1->2->3->4
（i）假设1->2->3->4已经反转好，成为4->3->2->1，然后将4->3->2->1看成一个整体，让这个整体的next指向null；
（ii）假设2->3->4已经反转好，已经成为了4->3->2, 然后将4->3->2看成一个整体，让这个整体的next指向1；
（iii）接下来问题变成了反转2->3->4
假设3->4已经反转好，已经成为了4->3, 然后将4->3看成一个整体，让这个整体的next指向2；
（iv）然后问题变成了反转3->4
假设4(实际上是4->NULL)已经反转好，已经成为了4(其实是head->4), 然后将4(其实是head->4)看成一个整体，让这个整体的next指向3；
（v）然后问题变成了反转4，head->4。
// Definition for singly-linked list.
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode reverseList(ListNode head) {
if (head == null ||head.next == null) {
return head;
}
ListNode nextNode = head.next;
head.next = null;
ListNode rest = reverseList(nextNode);
nextNode.next = head;
return rest;
}
Unit 3 Practice III
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
- Use two pointers, slower and faster.
- Slower moves step by step. faster moves two steps at the same time.
- If the Linked List has a cycle slower and faster will meet at some point.
public boolean hasCycle(ListNode head) {
if(head == null) {
return false;
}
ListNode slower = head;
ListNode faster = head;
while(faster.next != null && faster.next.next!= null) {
slower = slower.next;
faster = faster.next.next;
if (slower == faster) {
return true;
}
}
return false;
}
Unit 4 Practice IV
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
- The key to solve the problem is defining a fake head.
- Then compare the first elements from each list.
- Add the smaller one to the merged list.
- Finally, when one of them is empty, simply append it to the merged list, since it is already sorted.
class ListNode {
int val;
ListNode next;
ListNode (int x) {
val = x;
}
public static ListNode mergeTwoListNode (ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode result = head;
while (l1 != null || l2 != null) {
if (l1 != null && l2 != null) {
if (l1.val < l2.val) {
result.next = l1;
l1 = l1.next;
}
else{
result.next = l2;
l2 = l2.next;
}
result = result.next;
}
else if (l1 == null) {
result.next = l2;
break;
}
else if (l2 == null) {
result.next = l1;
break;
}
}
return head.next;
}
public static void main (String args[]) {
ListNode l1 = new ListNode(1);
l1.next = new ListNode(3);
l1.next.next = new ListNode(5);
l1.next.next.next = new ListNode(7);
ListNode l2 = new ListNode(2);
l2.next = new ListNode(4);
l2.next.next = new ListNode(6);
l2.next.next.next = new ListNode(8);
ListNode result = mergeTwoListNode(l1, l2);
while (result != null) {
System.out.print (result.val + " ");
result = result.next;
}
System.out.println();
}
}
Unit 5 Practice V
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed. (意思就是不允许换值)
- SwapNodesInPairs.jpg
class ListNode {
int val;
ListNode next;
ListNode (int x) {
val = x;
}
public static ListNode swapPairs(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode node = dummy;
while(head != null && head.next != null){
node.next = head.next;
head.next = node.next.next;
node.next.next = head;
node = head;
head = head.next;
}
return dummy.next;
}
public static void main (String args[]) {
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
ListNode result = swapPairs(head);
while (result != null) {
System.out.print (result.val + " ");
result = result.next;
}
System.out.println();
}
}
