欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LintCode: 99. 重排链表

程序员文章站 2022-07-15 23:24:27
...

题目:

LintCode: 99. 重排链表

分析:

首先想到将链表L按照这个规律重新赋值一遍,但题中说不能改变结点的值,然后想到将链表反转后重新链接起来。

以1->2->3->4为例

LintCode: 99. 重排链表

按虚线走,形成1->4->2->3->3->2->4->1,若是节点的值都不相同,则遇到相同时,就可以断开形成,若是有相同结点的值,也可以先统计结点个数,然后判断终止条件。但这样就需要新建一个链表。所以想到将链表一分为二,反转后半段,然后重新链接起来,依旧是1->4->2->3.

LintCode: 99. 重排链表

这样思路就来了:

  1. 将链表一分为二,找到中间结点。用到快慢指针。1->2->3->4,偶数个数点中间mid结点为2;1->2->3->4->5,奇数个数点中间mid结点为3。
  2. 反转mid结点之后的所有结点。
  3. 将两链表链接起来。
/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param head: The head of linked list.
     * @return: nothing
     */
    public void reorderList(ListNode head) {
        // write your code here
        if(head==null)  return;
        ListNode mid=findMid(head);
        ListNode head2=reverse(mid.next);
        mid.next=null;  //把前半段最后一个节点的next结点置为null;
        merge(head,head2);
    }

    public ListNode reverse(ListNode head){
        ListNode newHead=null;
        while(head!=null){
            ListNode temp=head.next;
            head.next=newHead;
            newHead=head;
            head=temp;
        }
        return newHead;
    }

    public void merge(ListNode head1,ListNode head2){
        int index=0;
        ListNode temp=new ListNode(0);
        while (head1!=null && head2!=null){
            if(index%2==0){
                temp.next=head1;
                head1=head1.next;
            }else{
                temp.next=head2;
                head2=head2.next;
            }
            temp=temp.next;
            index++;
        }
        if(head1==null){
            temp.next=head2;
        }
        if(head2==null){
            temp.next=head1;
        }
    }

    //找到中间结点
    public ListNode findMid(ListNode head){
        ListNode slow=head;ListNode fast=head.next;
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }
}