单链表反转问题

基本问题

如何将单链表反转?

单链表结构定义

/**
 * 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;
    }
}

算法实现

/**
 *
 * Description: 单链表反转.
 *
 * @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;
}

进阶问题

如何将单链表在指定区间内进行反转?

问题分析

这个问题是上面问题的一个变形,难度也加大了不少,主要的难点之处就在于对边界条件的检查。
实现思路,主要就是按照给定的区间得到需要整体反转的一个子链表然后进行反转,最后就是把链表按正确的顺序拼接在一起。

算法实现


/**
 *
 * Description: 单链表反转,反转制定区间内的节点.
 *
 * @param  head
 * @param  m
 * @param  n
 * @return  ListNode
 */
public   static  ListNode reverseBetween(ListNode head,  int  m,  int  n)
{
    // 合法性检测
    if  (head ==  null  || m >= n || m < 1 || n < 1) {
        return  head;
    }
    /**
    * 将链表按[m,n]区间分成三段.
    *
    * first,second,third分别为每一段的头节点(注意,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 ;
    }
    // 进行中间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;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 转载请注明出处:http://www.jianshu.com/p/c65d9d753c31 在上一篇博客《数据结构...
    Alent阅读 3,542评论 4 74
  • 1、用C语言实现一个revert函数,它的功能是将输入的字符串在原串上倒序后返回。 2、用C语言实现函数void ...
    希崽家的小哲阅读 6,368评论 0 12
  • 两年前,我学会了玩微信,对于这个新鲜事物我格外的释爱。 在2014年腊月的某个夜晚21:19分,我打开了微信,点进...
    姜西二阅读 160评论 0 0
  • 回忆就像是沙漏里蓝色的流沙,细腻,柔软。疼痛缠绵成根根细线,紧紧束缚着过去,不肯放开。已经很久没有想你了,直到现在...
    绫辻阅读 459评论 0 4
  • 晨。阳光很好。透过窗的缝隙照到心里。暖暖的。 空气中弥漫着甜蜜的情歌。痴笑着向那些所谓的忧伤潇洒告别。微凉的指尖开...
    爱刘同的考研er阅读 303评论 0 3