Leetcode[92, 25, 206] Reverse Linked List
06 Nov 2015###Task1 Reverse a singly linked list.
click to show more hints.
Hint: A linked list can be reversed either iteratively or recursively. Could you implement both?
###Python ####iterative
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None or head.next == None:
return head
prev = None
while head:
temp = head.next
head.next = prev
prev = head
head = temp
return prev
####recursive
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None or head.next == None:
return head
temp = head.next
post = self.reverseList(head.next)
head.next = None
temp.next = head
return post
###Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode temp = head.next;
ListNode second = reverseList(temp);
head.next = null;
temp.next = head;
return second;
}
}
###Points
- Iter: while loop stops when pointer reaches None instead of last node(in which case the last node still points to None)
- When do this recursively, we can temporarily save head.next
- while head -> reach None; while head.next -> reach last node
- O(n)
###Task2 Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example: Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.
###Python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
if head == None or head.next == None:
return head
dummy = ListNode(0)
dummy.next = head
head = dummy
for i in range(1, m):
head = head.next
pre = head
mNode = head.next
nNode = head.next
post = nNode.next
for i in range(m, n):
temp = post.next
post.next = nNode
nNode = post
post = temp
pre.next = nNode
mNode.next = post
return dummy.next
###Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null) {
return null;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
for (int i = 1; i < m; i++) {
head = head.next;
}
ListNode prev = head;
ListNode mNode = head.next;
ListNode nNode = mNode;
ListNode post = nNode.next;
for (int i = m; i < n; i++) {
ListNode temp = post.next;
post.next = nNode;
nNode = post;
post = temp;
}
prev.next = nNode;
mNode.next = post;
return dummy.next;
}
}
###Points
- head change -> dummy
- find the start point and then reverse, use the number of reverses to control this process; previously, wait until pointer reach the end of list
###Task3 Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example, Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
###Python
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
#注意这个和单纯的reverse的qubie
#这里，prev始终指向某一个group的最后一个节点
#而只reverse的题目里，prev就是某一个遍历过程中的点
class Solution(object):
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if head is None:
return head
if k == 0 or k == 1:
return head
dummy = ListNode(0)
dummy.next = head
prev = dummy
i = 0
while head:
i += 1
if i % k == 0:
prev = self.reverseHelper(prev, head.next)
head = prev.next
else:
head = head.next
return dummy.next
def reverseHelper(self, prev, next):
last = prev.next
cur = last.next
while cur != next:
last.next = cur.next
cur.next = prev.next
prev.next = cur
cur = last.next
return last
###Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverse(ListNode prev, ListNode next) {
ListNode last = prev.next; // the first one is guaranteed to be the last
ListNode cur = last.next;
while (last != next) {
ListNode temp = last.next;
last.next = prev;
prev = last;
last = temp;
}
return prev;
}
public ListNode reverseKGroup(ListNode head, int k) {
//the point is find how to reverse between two arbitrary nodes
//edge cases
if (head == null) return null;
if (k == 0 || k == 1) return head;
//dummy node
ListNode dummy = new ListNode(0);
ListNode pre = dummy;
dummy.next = head;
int i = 0;
while (head != null) {
i++;
if (i % k == 0) {
pre = reverse(pre, head.next);
head = pre.next;
} else {
head = head.next;
}
}
return dummy.next;
}
}
###Points
- Diff: when to break out of the loop? until reach certain node
- Need to return the tail node in each group in order to concatenate the rest of nodes.