基本問(wèn)題
如何將單鏈表反轉(zhuǎn)姜性？
單鏈表結(jié)構(gòu)定義
/**
* Description: Definition for singly-linked list.
*
* @author: crane-yuan
* @date: 2016-9-17 下午12:11:13
*/
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) {
val = x;
}
}
算法實(shí)現(xiàn)
/**
*
* Description: 單鏈表反轉(zhuǎn).
*
* @param head
* @return ListNode
*/
public static ListNode reverseList(ListNode head)
{
if (head == null ) {
return head;
}
ListNode prev = null ;
ListNode current = head;
ListNode next = null ;
while (current != null ) {
next = current. next ;
current. next = prev;
prev = current;
current = next;
}
head = prev;
return head;
}
進(jìn)階問(wèn)題
如何將單鏈表在指定區(qū)間內(nèi)進(jìn)行反轉(zhuǎn)？
問(wèn)題分析
這個(gè)問(wèn)題是上面問(wèn)題的一個(gè)變形，難度也加大了不少，主要的難點(diǎn)之處就在于對(duì)邊界條件的檢查觉渴。
實(shí)現(xiàn)思路，主要就是按照給定的區(qū)間得到需要整體反轉(zhuǎn)的一個(gè)子鏈表然后進(jìn)行反轉(zhuǎn)徽惋，最后就是把鏈表按正確的順序拼接在一起案淋。
算法實(shí)現(xiàn)
/**
*
* Description: 單鏈表反轉(zhuǎn)，反轉(zhuǎn)制定區(qū)間內(nèi)的節(jié)點(diǎn).
*
* @param head
* @param m
* @param n
* @return ListNode
*/
public static ListNode reverseBetween(ListNode head, int m, int n)
{
// 合法性檢測(cè)
if (head == null || m >= n || m < 1 || n < 1) {
return head;
}
/**
* 將鏈表按[m,n]區(qū)間分成三段.
*
* first,second,third分別為每一段的頭節(jié)點(diǎn)(注意险绘，m=1也就是first與second相等的情況的處理)
* first --> firstTail
* second
* third
*/
ListNode first = head;
ListNode firstTail = first;
ListNode second = first;
ListNode third = first;
ListNode current = first;
int i = 0;
while (current != null ) {
i++;
if (i == m - 1) {
firstTail = current;
}
if (i == m) {
second = current;
}
if (i == n) {
third = current. next ;
break ;
}
current = current. next ;
}
// 進(jìn)行中間second段的reverse
current = second;
ListNode prev = third;
ListNode next = null ;
while (current != third) {
next = current. next ;
current. next = prev;
prev = current;
current = next;
}
if (m == 1) {
first = prev;
} else {
firstTail. next = prev;
}
return first;
}
